On the k-server conjecture

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the k-server conjecture

Full text

Pdf (381 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

Pages: 507 - 511

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Elias Koutsoupias	University of California, San Diego
Christos Papadimitriou	University of California, San Diego

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 15, Citation Count: 12

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/195058.195245 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	S. Ben-David , A. Borodin , R. Karp , G. Tardos , A. Wigderson, On the power of randomization in online algorithms, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.379-386, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100268]
	2	M. Chrobak and L.L. Larmore. The server problem and on-line games. In L.A. MeGeoeh and D.D. Sleator, editors, On-line Algorithms: proceedings of a DIMA US workshop, pages 11-64, 1991.
	3	A. Fiat, Y. Rabani, and Y. Ravid. Competitive kserver algorithms. Proceedings. 31st Annual Symposium on Foundations of Computer Science, pages 454-63 vol.2, 1990.
	4	E.F. Grove. The harmonic online k-server algorithm is competitive. In L.A. McGeoch and D.D. Sleator, editors, On-line Algorithms: proceedings of a DI- MA US workshop, pages 65-75, 1991.
	5	E. Koutsoupias and C. H. Papadimitriou. The kserver conjecture for k + 2 points. In preparation.
	6	Mark S. Manasse , Lyle A. McGeoch , Daniel D. Sleator, Competitive algorithms for server problems, Journal of Algorithms, v.11 n.2, p.208-230, Jun. 1990 [doi>10.1016/0196-6774(90)90003-W]

CITED BY 13

	Elias Koutsoupias , Christos H. Papadimitriou, On the k-server conjecture, Journal of the ACM (JACM), v.42 n.5, p.971-983, Sept. 1995
	Michael C. Loui, Strategic directions in research in theory of computing, ACM Computing Surveys (CSUR), v.28 n.4, p.575-590, Dec. 1996
	Moses Charikar , Dan Halperin , Rajeev Motwani, The dynamic servers problem, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.410-419, January 25-27, 1998, San Francisco, California, United States
	Houman Alborzi , Eric Torng , Patchrawat Uthaisombut , Stephen Wagner, The k-client problem, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.73-82, January 05-07, 1997, New Orleans, Louisiana, 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
	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
	Wolfgang W. Bein , Marek Chrobak , Lawrence L. Larmore, The 3-server problem in the plane, Theoretical Computer Science, v.289 n.1, p.335-354, 23 October 2002
	Kazuo Iwama , Kouki Yonezawa, The orthogonal CNN problem, Information Processing Letters, v.90 n.3, p.115-120, 16 May 2004
	Elias Koutsoupias , David Scot Taylor, The CNN problem and other k-server variants, Theoretical Computer Science, v.324 n.2-3, p.347-359, 20 September 2004
	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
	William F. Klostermeyer , Kankanahalli Srinivas, Reducing disk power consumption in a portable computer, ACM SIGOPS Operating Systems Review, v.29 n.2, p.27-32, April 1995
	Weimin Ma , Yinfeng Xu , Kanliang Wang, On-line k-Truck Problem and Its Competitive Algorithms, Journal of Global Optimization, v.21 n.1, p.15-25, September 2001
	P. Raghavan , M. Snir, Memory versus randomization in on-line algorithms, IBM Journal of Research and Development, v.38 n.6, p.683-707, Nov. 1994