iii Contents
1Cover Page
i
2Project Summary
ii
3Table of Contents
iii
Contents
1Cover Page i 2Project Summary ii 3Table of Contents iii 4Objectives and Aims1 5Narrative and Bibliography2
5.1Rationale of the Project (2)
5.1.1Current Status (2)
5.1.2Barriers (2)
5.1.3Plan (3)
5.2Research Plan (3)
5.2.1NP-Hard Problems (4)
5.2.2Online Problems (5)
5.2.3Approximation Algorithms (6)
5.2.4Previous and Ongoing Work (7)
5.2.5Planned Work (7)
5.2.6Plans for Publication (8)
5.2.7Comparison (9)
5.2.8Plans for Further Funding (9)
5.2.9Schedule (10)
5.3Involvement and Quali?cations of Investigators,Other Faculty,and
Students (10)
5.4Institutional Capabilities and Commitment (11)
5.5Bibliography (11)
6Budget and Budget Narrative16
6.1Form5-R&D,Year1 (16)
6.2Form5-R&D,Year2 (17)
6.3Form5-R&D,Year3 (18)
6.4Form5-R&D,Composite (19)
6.5Justi?cation for Year1 (20)
6.6Justi?cation for Year2 (21)
6.7Justi?cation for Year3 (22)
iii
7Current and Pending Support/History of Support23
7.1Form3 (23)
7.2Form7 (24)
8Biographical Sketch25
iv
4Objectives and Aims
The objective of this grant is provide the PI with extra support,beyond what is available from his department,enabling him to better conduct fundamental research in computer science.
More speci?cally,research will be conducted in the area of approximation algo-rithms,an area of growing importance within theoretical computer science.The goal of this research area is to?nd approximate solutions to computational problems which are di?cult or impossible to solve exactly.This type of research is applicable in a number of important areas including:computer systems(caching policies,CPU scheduling et cetera),the Internet(data distribution,web caching,routing et cetera), telecommunications(call admission,routing,et cetera)and manufacturing(machine scheduling,planning et cetera).
The extra support will:
?Provide the PI with a full12-month salary for the next two years and11months of salary during the third year.
?Allow the PI to travel to2conferences during the year,enabling him to present his research and interact with other investigators in his area.
?Let the PI make one long term visit to another institution during the summer months.
?Provide the PI with supplies necessary for publishing papers(paper,laser toner, et cetera).
?Allow the PI to hire one graduate assistant,who will aid the PI in his work, and be trained in the area of approximation algorithms.
These will enable the PI to maintain a high level of productivity in research.
The goal is to publish3or more articles each year,either in refereed conferences or in journals.This will bring recognition to the PI,Louisiana State University, and the State of Louisiana.Further,this will help the PI to build his reputation as researcher—enabling him to better compete for federal funding.
1
5Narrative and Bibliography
5.1Rationale of the Project
In this section,we explain the current status of the PI’s research,identify barriers which might keep him from continuing his research,and outline a plan to overcome the listed barriers.
5.1.1Current Status
The PI is currently an active researcher in the?eld of online algorithms.In that area,he has6refereed journal publications,6refereed conference publications and several investigations in progress(he has also worked in other areas).He received his Ph.D.from the University of California,Irvine in1997.During the period be-tween August1997and September1998he worked as a post-doctoral researcher under Gerhard Woeginger,a well respected researcher in the area of approximation and online algorithms,as part of the START program Y43-MAT“Combinatorial approximation algorithms”of the Austrian Ministry of Science.During the period between September1998and August1999,he held a post-doctoral fellowship at the Max-Planck-Institute for Computer Science.He has collaborated with researchers in California,Austria,Germany,Israel,The Czech Republic,Argentina,and Canada. His current investigations keep him in contact with several of these past collabora-tors.In conclusion,the PI already has the beginnings of a research program in online algorithms underway.
The PI is currently trying to branch out from online algorithms;he is making initial investigations into the closely related area of approximation algorithms for NP-hard problems.
5.1.2Barriers
The main barrier,which could prevent the PI from continuing his ongoing investiga-tions and from exploring new areas,is lack of funding to support research,travel and publication.
?If the PI has no summer salary,he may not be able to devote all of his summer time to research.
?If the PI has no money to travel to conferences,he will be unable to present his research.
?If the PI has no money to visit colleagues,he will be unable to collaborate e?ectively.
2
?If the PI has no money to buy supplies such as laser toner and paper,he will have to make do with what his department can provide him.
?If the PI has no money for purchasing books and conference proceedings,he will have to rely on his university’s library,which may not purchase the materials he needs.
The PI has been employed in Europe during the past two years,and thus has active collaborations with colleagues there.The PI would like to sustain these relationships, as they have proved fruitful in the past.
The main barrier preventing the PI from getting funding from federal agencies (such as NSF)is his junior status as a researcher.To get federal funding,he must complete against well established researchers from the major computer science uni-versities(University of California,MIT,Stanford,CMU,University of Illinois,et cetera).
5.1.3Plan
This proposal,if funded,will provide the PI with the funding he needs to overcome the aforementioned barriers,and establish himself as a more prominent researcher—one who can more easily obtain funding from federal agencies.Speci?cally,the proposal will
?Provide summer salary to the PI for its duration.
?Allow the PI to travel to two conferences each year(or to send a graduate student)in order to present results and to interact with fellow researchers.
?Permit the PI to travel to another institution each summer.
?Provide the PI with basic supplies.
?Allow the PI to buy books and conference proceedings.
?Allow the PI to hire a graduate assistant.
The proposal would cover a time period of three years.
5.2Research Plan
The study of approximation algorithms is an active area of computer science[29]. As the name suggests,an approximation algorithm is an algorithm that produces an approximate solution.We make this more formal in the sections to follow.
3
Approximation algorithms are of interest when the problem at hand cannot be
solved exactly.There are many reasons why this might be the case.We focus on two
types of such problems:NP-hard problems and online problems.
In this section,we provide an overview of the research the PI will conduct under
this proposal.It is organized as follows.We?rst explain what is meant by both
NP-hard and online,and what we mean precisely by approximation algorithm.We
then describe the past and ongoing research of the PI,followed by his plans for future
research and publication.We next relate this research to the current state of the art,
and to research going on at other institutions.Finally,we give a schedule for this
proposal.
5.2.1NP-Hard Problems
We do not go into the technical de?nition of NP-hardness.For that,we refer the
reader to the classic text of Garey and Johnson[27].For our purposes,it su?ces to
say that no NP-hard problem is known to admit an e?cient solution.By e?cient
solution,we mean an algorithm which is guaranteed to?nd an exact solution in
time polynomial in the size of the input.Further,none of these problems can admit
a polynomial time solution unless P=NP.The question of P=NP is a long
standing open problem in computer science[27].There are a large number of NP-
hard problems,many of which are of great practical interest.Some examples are ?Assigning jobs with?xed running times to machines in order to minimize the completion time of the last job[36].A great number of other scheduling prob-
lems of this type are also NP-hard[29].
?Finding the shortest tour for a traveling salesman who must visit each city from some?xed set exactly once[36].
?Finding the packing of items into?xed size bins which minimizes the number of bins used[27].
Because none of these problems can be solved e?ciently(given our current level
of knowledge),we consider approximate solutions.For a more complete introduc-
tion to the subject of approximation algorithms,we refer the reader to the book of
Hochbaum[29].Formally,a polynomial-time approximation algorithm:?Runs in time polynomial in the size of the input;
?for some constant c>1,Produces a solution with cost at most c times the cost of the best possible solution.
4
Algorithms which run in polynomial time are considered to be computationally e?-cient,whereas algorithms which take super-polynomial time are not[27].The value c in the preceding de?nition is called the approximation factor or the performance guarantee.One possible goal is to?nd,for a given problem,the polynomial-time approximation algorithm with lowest possible approximation factor.However,in cer-tain situations the main concern may be to?nd an approximation algorithm with fast running time or low memory usage.I.e.it is also important to consider the tradeo?between resource usage and the approximation factor.
For certain problems,it is possible to develop a better type of approximation algorithm.A polynomial-time approximation scheme(PTAS)takes a real valued parameter >0and
?Runs in time polynomial in the size of the input(when is considered to be a constant);
?Produces a solution produced with cost at most1+ times the cost of the best possible solution.
A fully polynomial-time approximation scheme(FPTAS)gives an even stronger guar-antee on running time,namely the running time is also polynomial in1/ .
Certain problems admit a FPTAS,while other admit only a PTAS or an approx-imation scheme.I.e.for certain problems it is possible to prove that no FPTAS(or PTAS)exists unless P=NP.
5.2.2Online Problems
An online algorithm is an algorithm which works under the handicap of an uncertain future[8,25].The problem to be solved is revealed to the algorithm incrementally,and the algorithm’s solution must also be produced incrementally.An online algorithm su?ers the same handicap as a person who gets up in the morning:He or she must plan the day without knowledge of events that will occur(and which could a?ect the plan).Many fundamental problems directly related to the performance of computer systems are online.Examples include:
?Deciding which variables to keep in the cache(fast memory)during the execu-tion of a program so as to maximize cache utilization[56,9,21,40,30];
?Deciding which web pages to keep in the cache of a web browser[28,59];
?Deciding how to distribute data on a network so as to minimize network tra?c or response time[34,58,3,13];
5
?Deciding how to schedule a job when future jobs are unknown so as to optimize
a given criteria[1,33,5].
In addition,many problems from other areas,such as telecommunications,stock market forecasting,exploration/navigation,and operations research,are also online. Thus the study of online algorithms is of great practical interest.In order to contrast them with online algorithms,algorithms which are not restricted in this way are called o?ine algorithms.
In competitive analysis the performance of an online algorithm is compared to that of the optimal o?ine algorithm[56].An online algorithm for a given problem is said to be c-competitive if for all problem instances the cost incurred by the algorithm is at most c times the cost incurred by the optimal o?ine algorithm on that same problem instance.Note that the value c is the same as the previously de?ned approx-imation factor.An online algorithm which is c-competitive for some c is known as a competitive online algorithm.The di?erence between a competitive online algorithm and a polynomial-time approximation algorithm is that the online algorithm is not required to run in polynomial time.(However,many competitive online algorithms do run in polynomial time.)
Recent research has focused on the use of randomization by online algorithms.
A randomized online algorithm is one which uses random coin?ips in its decision making[41].In this case,competitiveness is de?ned using average(expected)cost instead of cost.An algorithm which does not use randomization is a deterministic algorithm.For several online problems,randomization has yielded algorithms which out-perform their deterministic counterparts.However,for many problems it is the case that an optimal deterministic algorithm is known,but no known randomized algorithm out-performs this best deterministic algorithm.
5.2.3Approximation Algorithms
We refer collectively to algorithms which are polynomial time approximation algo-rithms or competitive online algorithms as approximation algorithms.Two types of results are sought.The?rst is rigorous proof that an algorithm for a particular problem is an approximation algorithm;this is an upper bound proof.The second is proof that no approximation algorithm can guarantee an approximation factor lower than a given value;this is a lower bound proof.(For online problems this means no online approximation algorithm is c-competitive.For NP-hard problems it means no polynomial-time approximation algorithm with approximation factor c exists unless P=NP.)The goal is to?nd matching upper and lower bounds for a given problem.
6
5.2.4Previous and Ongoing Work
The PI’s recent work has focused on competitive online algorithms.Problems investi-gated include:the metrical task system problem,the multi-threaded paging problem, the page replication problem and assorted scheduling problems.For the metrical task system problem,Sandra Irani and the PI developed the?rst randomized online algo-rithm for general metric spaces[32].They also exhibited a near optimal algorithm for the uniform metric[32].In addition,the PI has shown how to apply randomization in a divide and conquer fashion to certain metric spaces[52].For the online multi-threaded paging problem the PI has shown an algorithm which is optimal to within a constant factor[50].Along with Shai Ben-David,Eli Dichterman and John Noga, the PI looked at the question of limited randomization[6].Several di?erent online scheduling problems were investigated,including:multiprocessor scheduling[42,44], multiprocessor scheduling with rejection[45],interval scheduling[49],scheduling with delivery times[44],scheduling on machines which run at di?erent speeds[19],and scheduling when the online restriction is loosened[54].Investigations currently un-derway include:algorithms for online page replication[26]and general techniques for proving lower bounds for online algorithms[53].
5.2.5Planned Work
In addition to continuing his ongoing research,the PI has plans to investigate the following problems in the near future:
?Paging and caching are some of the most fundamental and practical online problems in computer science.The advent of the world wide web has brought about a new wave of interest in such problems,as caching strategies have the potential to greatly decrease web page access times.Some initial research on online web caching has been done[28,59],however,there are great number of problems left to be explored.
?Scheduling involves the assignment of tasks to resources.Scheduling problems are ubiquitous.The tasks could be the running of a computer program,the manufacture of a car part,the playing of a baseball game,et cetera.The resources might be CPUs,factory machines,playing?elds,et cetera.There are an extremely large number of situations that?t into this framework[29].
In the o?ine scenario,where all tasks are known in advance,many scheduling problems turn out to be NP-hard.Approximation algorithms for scheduling is thus one area of keen interest for the PI.
?It is also possible to consider online scheduling.One area which contains a large number of open problems is randomized online scheduling[55].The PI has had
7
success with a number of problems in this area in the past[46,44,51,49],and plans to continue this line of work.
?There are two models of online scheduling.The?rst is where the jobs must be scheduled in a particular order—each must be scheduled before the next is revealed.The second and more realistic model is where jobs arrive over time—each job has a speci?c arrival time before which it is unknown to the scheduler.
Past research has focused mainly on the?rst model.The PI has done some work on the second model[51,42],and would like investigate it further.
?In the online bin-packing problem,one must assign items to bins of?xed capac-ity.Each item takes up a certain amount of space.An item must be irrevocably assigned to a bin before the next item is given.The status of this problem has not changed since1991[43].The PI has had success with computer assisted algorithm analysis in the past[48],and hopes that such methods will prove fruitful here.
?One general model which encompasses a large number of online problems(for instance many paging and caching problems)is the k-server problem[39].In this problem,there are k mobile servers in a metric space.A sequence of requests is given,each request being a point in the metric space.A server must be moved to meet each request.The problem is to minimize the total distance traveled by the servers.This problem has received a great deal of attention[2,4,7,10,11,12,14,15,17,18,22,23,24,31,35,37,38,39].
Almost all of this research has focused on deterministic algorithms.Very little progress has been made on randomized k-server algorithms.The PI hopes to make some investigations in this area.
?In a multi-threaded environment,there are several threads of execution running in parallel.Multi-threaded online paging has been investigated in[20,50,57].
In general,there are many online problems where inputs are being received from multiple sources(threads).The PI would like to further explore such problems. In addition,the funding provided under this proposal will help keep the PI informed about new developments and new open problems to be addressed.
5.2.6Plans for Publication
The goal of this proposal is to produce at least three papers each year,to be published in journals and/or refereed conference proceedings.Since attending a conference can be quite expensive(costs include:registration,hotel,plane tickets,food,taxi et cetera),the funding requested for travel is critical.Although most journals charge
8
no fee for publication,the PI must still have adequate supplies to prepare papers for submission(paper,laser toner et cetera).
5.2.7Comparison
Approximation algorithms is a thriving sub-area of theoretical computer science, which is in turn a core area of computer science.All of the major computer science departments in the United States(UC Berkeley,MIT,CMU,Stanford,Illinois)have faculty in the area of theoretical computer science,and many of them have someone investigating approximation algorithms.The interest in approximation algorithms is witnessed by the publication of several recent books in the area[8,25,29]and by specialized conferences and workshops:
?The APPROX‘98and APPROX‘99conferences.
?The Schloss Dagstuhl workshops on online algorithms held in1997and1999.
?A workshop and school on online algorithms held in Udine,Italy in1998.
?Several journal special issues devoted to approximation algorithms.
Before the arrival of the PI,in August1999,Louisiana State University had no computer science faculty in the core area of theoretical computer science.Having a strong researcher in theoretical computer science would almost certainly help the LSU Department of Computer Science gain international recognition.
The PI has distinguished himself from other researchers in the area of approxima-tion algorithms by:
?Focusing on the use of randomization[6,19,26,32,44,46,47,49,53,50,51, 52,54],which currently is poorly understood.
?Using computer aided analysis techniques to attack problems which are consid-ered to be very hard[19,44,46,47,48,51,54].
While the research approach of the PI is not totally unique,the group of researchers worldwide utilizing such approaches is quite small.
5.2.8Plans for Further Funding
The PI intends to apply for a grant from federal agencies such as NSF,ONR,DOD et cetera,so that he can continue his investigations once the three year period of this proposal expires.
9
5.2.9Schedule
The schedule for this project is as follows:
Date Event
June2000Project begins
June2000Hire graduate assistant
Summer2000Travel to the Technical University Graz(Austria)
June2000-May2001Attend two conferences
Summer2001Travel to visit colleagues
June2001-May2002Attend two conferences
Summer2002Travel to visit colleagues
June2002-May2003Attend two conferences
June2003Project ends
5.3Involvement and Quali?cations of Investigators,Other
Faculty,and Students
Steven Seiden(the PI)completed his Ph.D.in Information and Computer Science at the University of California,Irvine,in1997.His advisors were Dan Hirschberg and Sandy Irani.The subject of his dissertation was the use of randomization in the solution of online problems.During the1997/98academic year,he was a post-doc at the Technical University,Graz,where he worked with Professor Gerhard Woeginger, a recognized expert in the?eld of approximation algorithms for scheduling.During the1998/99academic year,he was a post-doc at the Max-Planck-Institute,where he worked in the Algorithms and Complexity Group of Professor Kurt Mehlhorn.He is now an Assistant Professor in the Department of Computer Science at Louisiana State University.He has published more than16articles in journals and refereed conference proceedings,12of those being speci?cally in the area of approximation algorithms.He has been working in that area for the last four years.
During the school year,the PI’s appointment is one-half teaching and one-half research.The PI will spend one half of his research time working on this proposal,if it is funded(i.e.%25of his time during the academic year).The money requested in this proposal will help him to make more e?ective use of his time during this period, allowing him to travel and meet with colleagues(at conferences).This will help him to keep abreast of new developments in the?eld and to stay in contact with potential collaborators.
The PI has been promised two months of summer salary for the?rst two years of his appointment as part of his hiring agreement.This proposal asks for an additional 1month salary for those?rst two years,and2months of summer salary for the
10
third year.This salary support will enable the PI to be involved in research full-time during these summer months.Part of the money requested will be used to visit other institutions for a prolonged period during the summer.
The graduate assistant funded by this proposal will be trained by the PI.
5.4Institutional Capabilities and Commitment
Louisiana State University and the LSU Department of Computer Science are com-mitted to building a strong research program in computer science.This demonstrated, for instance,by the PI’s light initial teaching load(2courses per year for the?rst2 years).
Insofar as equipment is concerned,the computing and other facilities provided by the Department of Computer Science are su?cient.No special equipment or facilities are needed for this type of research.
5.5Bibliography
[1]Albers,S.Better bounds for online scheduling.In Proceedings of the29th
ACM Symposium on Theory of Computing(1997),pp.130–139.
[2]Alon,N.,Karp,R.,Peleg,D.,and West,D.A graph-theoretic game
and its application to the k-server problem.SIAM Journal on Computing24,1 (Feb1995),78–100.
[3]Awerbuch,B.,Bartal,Y.,and Fiat,https://www.wendangku.net/doc/7f17455347.html,petitive distributed?le allo-
cation.In Proceedings of the25th ACM Symposium on the Theory of Computing (May1993),pp.164–173.
[4]Bartal,Y.,Chrobak,M.,and Larmore,L.L.A randomized algorithm
for two servers on the line.In Proceedings of the6th European Symposium on Algorithms(Aug1998),pp.247–258.
[5]Bartal,Y.,Fiat,A.,Karloff,H.,and Vohra,R.New algorithms for
an ancient scheduling problem.Journal of Computer and System Sciences51,3 (Dec1995),359–366.
[6]Ben-David,S.,Dichterman,E.,Noga,J.,and Seiden,S.S.On the
power of barely random online algorithms.Manuscript.
[7]Berman,P.,Karloff,H.,and Tardos,G.A competitive three-server
algorithm.In Proceedings of the1st ACM-SIAM Symposium on Discrete Algo-rithms(1990),pp.280–290.
11
[8]Borodin,A.,and El-Yaniv,R.Online Computation and Competitive Anal-
ysis.Cambridge University Press,1998.
[9]Borodin,A.,Irani,S.,Raghavan,P.,and Schieber,https://www.wendangku.net/doc/7f17455347.html,petitive
paging with locality of reference.Journal of Computer and System Sciences50, 2(Apr1995),244–258.
[10]Chrobak,M.,Karloff,H.,Payne,T.,and Vishwanathan,S.New
results on server problems.SIAM Journal on Discrete Mathematics4,2(May 1991),172–181.
[11]Chrobak,M.,and Larmore,L.A note on the server problem and a benev-
olent https://www.wendangku.net/doc/7f17455347.html,rmation Processing Letters38,4(May1991),173–5. [12]Chrobak,M.,and Larmore,L.Generosity helps or an11-competitive
algorithm for three servers.Journal of Algorithms16,2(Mar1994),234–63. [13]Chrobak,M.,Larmore,L.,Reingold,N.,and Westbrook,J.Page
migration algorithms using work functions.Journal of Algorithms24,1(Jul 1997),124–157.
[14]Chrobak,M.,and Larmore,L.L.A new approach to the server problem.
SIAM Journal on Discrete Mathematics4,3(Aug1991),323–328.
[15]Chrobak,M.,and Larmore,L.L.Server problems and on-line games.
In Proceedings of the DIMACS Workshop on On-line Algorithms(Feb1991), pp.11–64.
[16]Cormen,T.,Leiserson,C.,and Rivest,R.Introduction to Algorithms.
MIT Press,1990.
[17]Deng,X.,and Mahajan,S.Server problems and resistive https://www.wendangku.net/doc/7f17455347.html,rmation
Processing Letters37,4(Feb1991),193–196.
[18]El-Yaniv,R.,and Kleinberg,J.Geometric two-server https://www.wendangku.net/doc/7f17455347.html,r-
mation Processing Letters53,6(Mar1995),355–358.
[19]Epstein,L.,Noga,J.,Seiden,S.S.,Sgall,J.,and Woeginger,G.
Randomized online scheduling on two uniform machines.In Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms(Jan1999),pp.317–326.
[20]Feuerstein,E.,and Strejilevich de Loma,A.On multi-threaded paging.
In Proceedings of the7th International Symposium on Algorithms and Compu-tation(Dec1996),pp.417–426.
12
[21]Fiat,A.,Karp,R.,Luby,M.,McGeoch,L.,Sleator,D.,and Young,
https://www.wendangku.net/doc/7f17455347.html,petitive paging algorithms.Journal of Algorithms12,4(Dec1991),685–699.
[22]Fiat, A.,Rabani,Y.,and Ravid,https://www.wendangku.net/doc/7f17455347.html,petitive k-server algorithms.
Journal of Computer and System Sciences48,3(Jun1994),410–428.
[23]Fiat,A.,Rabani,Y.,Ravid,Y.,and Schieber,B.A deterministic O(k3)-
competitive k-server algorithm for the circle.Algorithmica11,6(Jun1994), 572–578.
[24]Fiat,A.,and Ricklin,https://www.wendangku.net/doc/7f17455347.html,petitive algorithms for the weighted server
problem.Theoretical Computer Science130,1(Aug1994),85–99.
[25]Fiat,A.,and Woeginger,G.,Eds.On-Line Algorithms—The State of the
Art.Lecture Notes in Computer Science.Springer-Verlag,1998.
[26]Fleischer,R.,and Seiden,S.S.Page replication—Variations on a theme.
Manuscript,1999.
[27]Garey,M.R.,and Johnson,https://www.wendangku.net/doc/7f17455347.html,puters and Intractability:A Guide
to the Theory of NP-completeness.W.H.Freeman and Company,1979.
[28]Irani,S.Page replacement with multi-size pages and applications to web
caching.In Proceedings of the29th ACM Symposium on the Theory of Com-puting(1997),pp.701–710.
[29]Irani,S.,and Karlin, A.Online computation.In Approximation Algo-
rithms for NP-hard Problems,D.Hochbuam,Ed.PWS Publishing Company, 1997,ch.13.
[30]Irani,S.,Karlin,A.,and Phillips,S.Strongly competitive algorithms for
paging with locality of reference.SIAM Journal on Computing25,3(Jun1996), 477–497.
[31]Irani,S.,and Rubinfeld,R.A competitive2-server https://www.wendangku.net/doc/7f17455347.html,rmation
Processing Letters39,2(Jul1991),85–91.
[32]Irani,S.,and Seiden,S.S.Randomized algorithms for metrical task systems.
Theoretical Computer Science194,1-2(Mar1998),163–182.
[33]Karger,D.,Phillips,S.,and Torng,E.A better algorithm for an ancient
scheduling problem.Journal of Algorithms20,2(Mar1996),400–430.
13
[34]Karlin,A.,Manasse,M.,Rudolph,L.,and Sleator,https://www.wendangku.net/doc/7f17455347.html,petitive
snoopy caching.Algorithmica3,1(1988),79–119.
[35]Karloff,H.,Rabani,Y.,and Ravid,Y.Lower bounds for randomized
k-server and motion-planning algorithms.SIAM Journal on Computing23,2 (Apr1994),293–312.
[36]Karp,R.M.Reducibility among combinatorial problems.In Complexity of
Computer Computations,https://www.wendangku.net/doc/7f17455347.html,ler and J.W.Thatcher,Eds.Plenum Press, New York,1972,pp.85–103.
[37]Kleinberg,J.A lower bound for two-server balancing https://www.wendangku.net/doc/7f17455347.html,rmation
Processing Letters52,1(Oct1994),39–43.
[38]Koutsoupias,E.,and Papadimitriou,C.On the k-server conjecture.Jour-
nal of the ACM42(1995),971–983.
[39]Manasse,M.,McGeoch,L.,and Sleator,https://www.wendangku.net/doc/7f17455347.html,petitive algorithms for
server problems.Journal of Algorithms11,2(Jun1990),208–230.
[40]McGeoch,L.,and Sleator,D.A strongly competitive randomized paging
algorithm.Algorithmica6,6(1991),816–825.
[41]Motwani,R.,and Raghavan,P.Randomized Algorithms.Cambridge Uni-
versity Press,1997.
[42]Noga,J.,and Seiden,S.S.Scheduling two machines with release times.In
Proceedings of the7th Conference on Integer Programming and Combinatorial Optimization(Jun1999),pp.391–399.
[43]Richey,M.B.Improved bounds for harmonic-based bin packing algorithms.
Discrete Applied Mathematics34(1991),203–227.
[44]Seiden,S.S.Randomized online multiprocessor scheduling.Algorithmica.To
appear.
[45]Seiden,S.S.More multiprocessor scheduling with rejection.Tech.Rep.Woe-
16,TU Graz,Institut f¨u r Mathematik B,1997.
[46]Seiden,S.S.Randomized algorithms for that ancient scheduling problem.In
Proceedings of the5th Workshop on Algorithms and Data Structures(Aug1997), pp.210–223.
14
[47]Seiden,S.S.Barely random algorithms for multiprocessor scheduling.Tech.
Rep.Woe-36,TU Graz,Institut f¨u r Mathematik B,1998.
[48]Seiden,S.S.Making the analysis of complicated algorithms fun:A mani-
festo for the computational method.In fun with Algorithms:Proceedings of the International Conference(Jun1998),pp.148–159.
[49]Seiden,S.S.Randomized preemptive online interval scheduling.Operations
Research Letters22,4-5(May1998),171–177.
[50]Seiden,S.S.Randomized online multi-threaded paging.Nordic Journal of
Computing6,2(1999),148–161.
[51]Seiden,S.S.Randomized online scheduling with delivery times.Journal of
Combinatorial Optimization3,4(Dec1999),399–416.
[52]Seiden,S.S.Unfair problems and randomized algorithms for metrical task
https://www.wendangku.net/doc/7f17455347.html,rmation and Computation148,2(Feb1999),219–240.
[53]Seiden,S.S.A guessing game and randomized online algorithms.In Proceed-
ings of the32nd Annual ACM Symposium on Theory of Computing(May2000).
To appear.
[54]Seiden,S.S.,Sgall,J.,and Woeginger,G.Semi-online scheduling with
decreasing job sizes.Tech.Rep.KAM-DIMATIA Series98-410,Charles Univer-sity,Prague,1998.
[55]Sgall,J.On-line scheduling.In On-Line Algorithms—The State of the Art,
A.Fiat and G.Woeginger,Eds.,Lecture Notes in Computer Science.Springer-
Verlag,1998,ch.9.
[56]Sleator,D.,and Tarjan,R.Amortized e?ciency of list update and paging
https://www.wendangku.net/doc/7f17455347.html,munications of the ACM28,2(Feb1985),202–208.
[57]Strejilevich de Loma,A.New results on fair multi-threaded paging.In
Proceedings of the1st Argentine Workshop on Theoretical Informatics(1997), pp.111–122.
[58]Westbrook,J.Randomized algorithms for multiprocessor page migration.
SIAM Journal on Computing23,5(Oct1994),951–965.
[59]Young,N. E.Online?le caching.In Proceedings of the9th ACM-SIAM
Symposium on Discrete Algorithms(1998),pp.82–86.
15