Competitive algorithms for on-line problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Competitive algorithms for on-line problems

Full text

Pdf (1.20 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twentieth annual ACM symposium on Theory of computing table of contents

Chicago, Illinois, United States

Pages: 322 - 333

Year of Publication: 1988

ISBN:0-89791-264-0

Authors

Mark Manasse	DEC Systems Research Center, 130 Lytton Avenue, Palo Alto, CA
Lyle McGeoch	Department of Mathematics, Amherst College, Amherst, MA
Daniel Sleator	Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 94, Citation Count: 56

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/62212.62243 What is a DOI?

ABSTRACT

An on-line problem is one in which an algorithm must handle a sequence of requests, satisfying each request without knowledge of the future requests. Examples of on-line problems include scheduling the motion of elevators, finding routes in networks, allocating cache memory, and maintaining dynamic data structures. A competitive algorithm for an on-line problem has the property that its performance on any sequence of requests is within a constant factor of the performance of any other algorithm on the same sequence. This paper presents several general results concerning competitive algorithms, as well as results on specific on-line problems.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. Borodin , N. Linial , M. Saks, An optimal online algorithm for metrical task systems, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.373-382, January 1987, New York, New York, United States [doi>10.1145/28395.28435]
	2	Jon L. Bentley , Catherine C. McGeoch, Amortized analyses of self-organizing sequential search heuristics, Communications of the ACM, v.28 n.4, p.404-411, April 1985 [doi>10.1145/3341.3349]
	3	Calderbank, A. R., Coffman, Jr., E. G., and Flatto, L. Sequencing problems in two-server systems. Mathematics of Operations Research, 10(4):585-598, November 1985.
	4	Calderbank, A. R., Coffman, Jr., E. G., and Flatto, L. Sequencing two servers on a sphere. Commun. Statist.-Stochastic Models, 1 (1): 17- 28, November 1985.
	5	Karlin, A. R., Manasse, M. S., Rudolph, L., and $1eator, D. D. Competitive Snoopy Caching. Computer Science Technical Report CMU-CS- 86-164, Carnegie Mellon University, 1986, (To appear in Algorithmica.
	6	Lyle Andrew Mcgeoch, Algorithms for two graph problems: computing maximum-genus imbeddings and the two-server problem, 1987
	7	Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]

CITED BY 56

	P. Berman , H. Karloff , G. Tardos, A competitive 3-server algorithm, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.280-290, January 22-24, 1990, San Francisco, California, United States
	M. Chrobak , H. Karloff , T. Payne , S. Vishwanathan, New results on server problems, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.291-300, January 22-24, 1990, San Francisco, California, United States
	M. Bern , D. H. Greene , A. Raghunathan , M. Sudan, Online algorithms for locating checkpoints, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.359-368, May 13-17, 1990, Baltimore, Maryland, United States
	Anna R. Karlin , Mark S. Manasse , Lyle A. McGeoch , Susan Owicki, Competitive randomized algorithms for non-uniform problems, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.301-309, January 22-24, 1990, San Francisco, California, United States
	Christos H. Papadimitriou , Mihalis Yannakakis, Linear programming without the matrix, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.121-129, May 16-18, 1993, San Diego, California, United States
	E. F. Grove, The harmonic online K-server algorithm is competitive, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.260-266, May 05-08, 1991, New Orleans, Louisiana, United States
	Sandy Irani , Nick Reingold , Jeffery Westbrook , Daniel D. Sleator, Randomized competitive algorithms for the list update problem, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.251-260, January 28-30, 1991, San Francisco, California, United States
	Neal Young, On-line caching as cache size varies, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.241-250, January 28-30, 1991, San Francisco, California, United States
	Baruch Awerbuch , David Peleg, Online tracking of mobile users, Journal of the ACM (JACM), v.42 n.5, p.1021-1058, Sept. 1995
	R. M. Karp , U. V. Vazirani , V. V. Vazirani, An optimal algorithm for on-line bipartite matching, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.352-358, May 13-17, 1990, Baltimore, Maryland, United States
	Xiaotie Deng , Nian Gu , Tim Brecht , KaiCheng Lu, Preemptive scheduling of parallel jobs on multiprocessors, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.159-167, January 28-30, 1996, Atlanta, Georgia, United States
	Yossi Azar , Joseph Naor , Raphael Rom, The competitiveness of on-line assignments, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.203-210, September 1992, Orlando, Florida, United States
	Beng-Hong Lim , Anant Agarwal, Reactive synchronization algorithms for multiprocessors, ACM SIGPLAN Notices, v.29 n.11, p.25-35, Nov. 1994
	Baruch Awerbuch , Yossi Azar , Yair Bartal, On-line generalized Steiner problem, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.68-74, January 28-30, 1996, Atlanta, Georgia, United States
	Carsten Lund , Nick Reingold, Linear programs for randomized on-line algorithms, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.382-391, January 23-25, 1994, Arlington, Virginia, United States
	Jeff Edmonds , Donald D. Chinn , Tim Brecht , Xiaotie Deng, Non-clairvoyant multiprocessor scheduling of jobs with changing execution characteristics (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.120-129, May 04-06, 1997, El Paso, Texas, United States
	Elias Koutsoupias , Christos H. Papadimitriou, On the k-server conjecture, Journal of the ACM (JACM), v.42 n.5, p.971-983, Sept. 1995
	Susanne Albers , Stefano Leonardi, On-line algorithms, ACM Computing Surveys (CSUR), v.31 n.3es, Sept. 1999
	Baruch Awerbuch , Yair Bartal , Amos Fiat, Competitive distributed file allocation, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.164-173, May 16-18, 1993, San Diego, California, United States
	William R. Burley , Sandy Irani, On algorithm design for metrical task systems, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.420-429, January 22-24, 1995, San Francisco, California, United States
	Yair Bartal , Amos Fiat , Yuval Rabani, Competitive algorithms for distributed data management (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.39-50, May 04-06, 1992, Victoria, British Columbia, Canada
	Yixiu Huang , Prasad Sistla , Ouri Wolfson, Data replication for mobile computers, ACM SIGMOD Record, v.23 n.2, p.13-24, June 1994
	Xiaotie Deng , Patrick Dymond, On multiprocessor system scheduling, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.82-88, June 24-26, 1996, Padua, Italy
	Anil Kamath , Omri Palmon , Serge Plotkin, Routing and admission control in general topology networks with Poisson arrivals, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.269-278, January 28-30, 1996, Atlanta, Georgia, United States
	Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States
	Todd Gormley , Nicholas Reingold , Eric Torng , Jeffery Westbrook, Generating adversaries for request-answer games, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.564-565, January 09-11, 2000, San Francisco, California, United States
	Jeffery Westbrook , Lenore Zuck, Adaptive algorithms for PASO systems, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.264-273, August 14-17, 1994, Los Angeles, California, United States
	Bala Kalyanasundaram , Kirk Pruhs, On-line weighted matching, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.234-240, January 28-30, 1991, San Francisco, California, United States
	James Aspnes , Yossi Azar , Amos Fiat , Serge Plotkin , Orli Waarts, On-line routing of virtual circuits with applications to load balancing and machine scheduling, Journal of the ACM (JACM), v.44 n.3, p.486-504, May 1997
	Xiaotie Deng , Sanjeev Mahajan, Infinite games: randomization, computability, and applications to online problems, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.289-298, May 05-08, 1991, New Orleans, Louisiana, United States
	Yair Bartal , Moses Charikar , Piotr Indyk, On page migration and other relaxed task systems, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.43-52, January 05-07, 1997, New Orleans, Louisiana, United States
	Baruch Awerbuch , Yair Bartal , Amos Fiat, Distributed paging for general networks, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.574-583, January 28-30, 1996, Atlanta, Georgia, United States
	D. Coppersmith , P. Doyle , P. Raghavan , M. Snir, Random walks on weighted graphs, and applications to on-line algorithms, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.369-378, May 13-17, 1990, Baltimore, Maryland, United States
	Enoch Peserico, The lazy adversary conjecture fails, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	Yair Bartal , Elias Koutsoupias, On the competitive ratio of the work function algorithm for the k-server problem, Theoretical Computer Science, v.324 n.2-3, p.337-345, 20 September 2004
	Ee-Chien Chang , Chee Yap, Competitive on-line scheduling with level of service, Journal of Scheduling, v.6 n.3, p.251-267, May/June 2003
	Amotz Bar-Noy , Baruch Schieber, The Canadian Traveller Problem, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.261-270, January 28-30, 1991, San Francisco, California, United States
	Michael T. Goodrich, Competitive tree-structured dictionaries, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.494-495, January 09-11, 2000, San Francisco, California, United States
	Michael G. Luby , Joseph (Seffi) Naor , Ariel Orda, Tight bounds for dynamic storage allocation, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.724-732, January 23-25, 1994, Arlington, Virginia, United States
	H. Ramesh, On traversing layered graphs on-line, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.412-421, January 25-27, 1993, Austin, Texas, United States
	Jeff Edmonds , Donald D. Chinn , Tim Brecht , Xiaotie Deng, Non-clair voy ant multiprocessor scheduling of jobs with changing execution characteristics, Journal of Scheduling, v.6 n.3, p.231-250, May/June 2003
	A. Prasad Sistla , Ouri Wolfson , Yixiu Huang, Minimization of Communication Cost Through Caching in Mobile Environments, IEEE Transactions on Parallel and Distributed Systems, v.9 n.4, p.378-390, April 1998
	Ouri Wolfson , Yixiu Huang, Competitive Analysis of Caching in Distributed Databases, IEEE Transactions on Parallel and Distributed Systems, v.9 n.4, p.391-409, April 1998
	Baruch Awerbuch , Yossi Azar , Yair Bartal, On-line generalized Steiner problem, Theoretical Computer Science, v.324 n.2-3, p.313-324, 20 September 2004
	Baruch Awerbuch , Yair Bartal , Amos Fiat, Competitive distributed file allocation, Information and Computation, v.185 n.1, p.1-40, August 25, 2003
	Stephen Hughes, A new bound for space bounded server algorithms, Proceedings of the 33rd annual on Southeast regional conference, March 17-18, 1995, Clemson, South Carolina
	Sunil Nakrani , Craig Tovey, On Honey Bees and Dynamic Server Allocation in Internet Hosting Centers, Adaptive Behavior - Animals, Animats, Software Agents, Robots, Adaptive Systems, v.12 n.3-4, p.223-240, September-December 2004
	Brian C. Forney , Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau, Storage-Aware Caching: Revisiting Caching for Heterogeneous Storage Systems, Proceedings of the 1st USENIX Conference on File and Storage Technologies, January 28-30, 2002, Monterey, CA
	Konstantinos Panagiotou , Alexander Souza, On adequate performance measures for paging, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Guido Schäfer , Naveen Sivadasan, Topology matters: smoothed competitiveness of metrical task systems, Theoretical Computer Science, v.341 n.1, p.216-246, 5 September 2005
	Rodney G. Downey , Catherine McCartin, Online promise problems with online width metrics, Journal of Computer and System Sciences, v.73 n.1, p.57-72, February, 2007
	Joan Boyar , Lene M. Favrholdt , Kim S. Larsen, The relative worst-order ratio applied to paging, Journal of Computer and System Sciences, v.73 n.5, p.818-843, August, 2007
	Amos Korman , Shay Kutten, Controller and estimator for dynamic networks, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Weimin Ma , James N. Liu , Guoqing Chen , Jane You, Competitive Analysis for the On-line Truck Transportation Problem, Journal of Global Optimization, v.34 n.4, p.489-502, April 2006
	Weimin Ma , Jane You , Yinfeng Xu , James Liu , Kanliang Wang, On the On-line Number of Snacks Problem, Journal of Global Optimization, v.24 n.4, p.449-462, December 2002
	Norman W. Paton , Jorge Buenabad-Chavez , Mengsong Chen , Vijayshankar Raman , Garret Swart , Inderpal Narang , Daniel M. Yellin , Alvaro A. Fernandes, Autonomic query parallelization using non-dedicated computers: an evaluation of adaptivity options, The VLDB Journal — The International Journal on Very Large Data Bases, v.18 n.1, p.119-140, January 2009