On-line algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On-line algorithms

Full text

Pdf (171 KB)

Source

ACM Computing Surveys (CSUR) archive
Volume 31 , Issue 3es (September 1999) table of contents

Article No. 4

Year of Publication: 1999

ISSN:0360-0300

Authors

Susanne Albers	Max-Planck-Institut für Informatik, Im Stadtwald, 66123 Saarbrücken, Germany
Stefano Leonardi	Dipartimento di Informatica e Sistemistica, Università a di Roma "La Sapienza", Via Salaria 113, 00198 Roma, Italy

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 106, Citation Count: 7

Additional Information:

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/333580.333583 What is a DOI?

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	Susanne Albers, Better bounds for online scheduling, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.130-139, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258566]
	2	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 [doi>10.1145/258128.258201]
	3	B. Awerbuch, Y. Azar and S. Plotkin. Throughput-competitive online routing. In 34th IEEE Symp. on Foundations of Computer Science, 32-40, 1993.
	4	Baruch Awerbuch , Yair Bartal , Amos Fiat , Adi Rosén, Competitive non-preemptive call control, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.312-320, January 23-25, 1994, Arlington, Virginia, United States
	5	B. Awerbuch, R. Gawlick, T. Leighton and Y. Rabani. On-line admission control and circuit routing for high performance computing and communication. In Proc. of the 35th Annual IEEE Syrup. on Foundations of Computer Science, 412-423, 1994.
	6	Y. Azar, A. Broder and A. Karlin. On-line load balancing. Proc. 36th IEEE Syrup. on Foundations of Computer Science, 218-225, 1992.
	7	Yossi Azar, On-line Load Balancing, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.178-195, January 1998
	8	Yossi Azar , Leah Epstein, On-Line Load Balancing of Temporary Tasks on Identical Machines, Proceedings of the Fifth Israel Symposium on the Theory of Computing Systems (ISTCS '97), p.119, June 17-19, 1997
	9	Yossi Azar , Bala Kalyanasundaram , Serge A. Plotkin , Kirk Pruhs , Orli Waarts, Online Load Balancing of Temporary Tasks, Proceedings of the Third Workshop on Algorithms and Data Structures, p.119-130, August 11-13, 1993
	10	Yair Bartal , Amos Fiat , Howard Karloff , Rakesh Vohra, New algorithms for an ancient scheduling problem, Journal of Computer and System Sciences, v.51 n.3, p.359-366, Dec. 1995 [doi>10.1006/jcss.1995.1074]
	11	Yair Bartal , Amos Fiat , Stefano Leonardi, Lower bounds for on-line graph problems with application to on-line circuit and optical routing, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.531-540, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238001]
	12	Yair Bartal , Stefano Leonardi, On-Line Routing in All-Optical Networks, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.516-526, July 07-11, 1997
	13	S. Ben-David, A. Borodin, R.M. Karp, G. Tardos and A. Wigderson. On the power of randomization in on-line algorithms. Algorithmica, 11:2-14,1994.
	14	Avrim Blum, On-line Algorithms in Machine Learning, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.306-325, January 1998
	15	Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
	16	Allan Borodin , Nathan Linial , Michael E. Saks, An optimal on-line algorithm for metrical task system, Journal of the ACM (JACM), v.39 n.4, p.745-763, Oct. 1992 [doi>10.1145/146585.146588]
	17	Allan Borodin , Prabhakar Raghavan , Sandy Irani , Baruch Schieber, Competitive paging with locality of reference, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.249-259, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103422]
	18	Nicolò Cesa-Bianchi , Yoav Freund , David P. Helmbold , David Haussler , Robert E. Schapire , Manfred K. Warmuth, How to use expert advice, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.382-391, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167198]
	19	Andrew Chou , Jeremy Cooperstock , Ran El-Yaniv , Michael Klugerman , Tom Leighton, The statistical adversary allows optimal money-making trading strategies, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.467-476, January 22-24, 1995, San Francisco, California, United States
	20	Amos Fiat , Anna R. Karlin, Randomized and multipointer paging with locality of reference, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.626-634, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225280]
	21	Amos Fiat , Ziv Rosen, Experimental studies of access graph based heuristics: beating the LRU standard?, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.63-72, January 05-07, 1997, New Orleans, Louisiana, United States
	22	J. Garay, I.S. Gopal, S. Kutten, Y. Mansour and M. Yung. Efficient online call control algorithms. In Proc. 2nd Israel Syrup. on Theory of Computing and Systems, 285-293, 1993.
	23	R. Gawlick, A. Kamath, S. Plotkin and K. Ramakrishnan. Routing and admission control of virtual circuits in general topology networks. Technical Report BL011212-940819- 19TM ATf~T Bell Laboratories, 1994.
	24	T. Gormley and E. Torng. Bounded online problems. Manuscript, 1998.
	25	R.L. Graham. Bounds for certain multiprocessor anomalies. Bell System Technical Journal, 45:1563-1581, 1966.
	26	Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	27	Sandy Irani , Anna R. Karlin , Steven Phillips, Strongly competitive algorithms for paging with locality of reference, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.228-236, September 1992, Orlando, Florida, United States
	28	David R. Karger , Steven J. Phillips , Eric Torng, A better algorithm for an ancient scheduling problem, Journal of Algorithms, v.20 n.2, p.400-430, March 1996 [doi>10.1006/jagm.1996.0019]
	29	A. Karlin, M. Manasse, L. Rudolph and D.D. Sleator. Competitive snoopy caching, Algorithmica, 3:79-119, 1988.
	30	J. Kzeinberg , E. Tardos, Disjoint paths in densely embedded graphs, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.52, October 23-25, 1995
	31	E. Koutsoupias and C.H. Papadimitriou. Beyond competitive analysis. In Proc. 34th Annual Symp. on Foundations of Computer Science, 394-400, 1994.
	32	Stefano Leonardi , Alberto Marchetti-Spaccamela , Alessio Presciutti , Adi Rosén, On-line randomized call control revisited, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.323-332, January 25-27, 1998, San Francisco, California, United States
	33	Stefano Leonardi, On-line Network Routing, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.242-267, January 1998
	34	Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
	35	Mark Manasse , Lyle McGeoch , Daniel Sleator, Competitive algorithms for on-line problems, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.322-333, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62243]
	36	Rajeev Motwani , Steven Phillips , Eric Torng, Non-clairvoyant scheduling, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.422-431, January 25-27, 1993, Austin, Texas, United States
	37	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
	38	P. Raghavan. A statistical adversary for on-line algorithms. In On-Line Algorithms, DI- MACS Series in Discrete Mathematics and Theoretical Computer Science, 79-83, 1991.
	39	J. SgM1. On-line scheduling. In Online Algorithms: The State of the Art, edited by A. Fiat and G. Woeginger, Springer LNCS, Volume 1442, 198-231, 1998.
	40	David B. Shmoys , Joel Wein , David P. Williamson, Scheduling Parallel Machines On-line, SIAM Journal on Computing, v.24 n.6, p.1313-1331, Dec. 1995 [doi>10.1137/S0097539793248317]
	41	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 7

	Martin Ziegler , Vasco Brattka, Computability in linear algebra, Theoretical Computer Science, v.326 n.1-3, p.187-211, 20 October 2004
	María Isabel Alfonso , Federico Barber, A Mixed Closure-CSP Method for Solving Scheduling Problems, Applied Intelligence, v.21 n.2, p.173-193, September-October 2004
	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
	Naveen Garg , Anupam Gupta , Stefano Leonardi , Piotr Sankowski, Stochastic analyses for online combinatorial optimization problems, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.942-951, January 20-22, 2008, San Francisco, California
	Alexandru Iosup , Dick H. J. Epema , Todd Tannenbaum , Matthew Farrellee , Miron Livny, Inter-operating grids through delegated matchmaking, Proceedings of the 2007 ACM/IEEE conference on Supercomputing, November 10-16, 2007, Reno, Nevada
	Alexandru Iosup , Todd Tannenbaum , Matthew Farrellee , Dick Epema , Miron Livny, Inter-operating grids through Delegated MatchMaking, Scientific Programming, v.16 n.2-3, p.233-253, April 2008
	Alexandru Iosup , Mathieu Jan , Ozan Sonmez , Dick H. J. Epema, On the dynamic resource availability in grids, Proceedings of the 8th IEEE/ACM International Conference on Grid Computing, p.26-33, September 19-21, 2007