AbstractWe prove that the work function algorithm for the k-server problem has competitive ratio at most 2k-1. Manasse, McGeoch, and Sleator [24] conjectured that the competitive ratio for the k-server problem is exactly k (it is trivially at least k); previously the best known upper bound was exponential in k. Our proof involves three crucial ingredients: A quasiconvexity property of work functions, a duality lemma that uses quasiconvexity to characterize the configurations that achieve maximum increase of the work function, and a potential function that exploits the duality lemma. Copyright 1995 by ACM, Inc.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Preliminary versionA preliminary version of these results was presented in: Elias Koutsoupias and Christos Papadimitriou. On the k-server conjecture. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 507-511, Montréal, Québec, Canada, 23-25 May 1994.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- computation on discrete structures; G.2.1 [Discrete Mathematics]: Combinatorics -- combinatorial algorithms
General Terms: Algorithms, theory, performance
Additional Key Words and Phrases: Competitive analysis, $k$-server problem, on-line algorithms, potential, quasiconvexity, work function
Selected papers that cite this one
- Yair Bartal, Avrim Blum, Carl Burch, and Andrew Tomkins. A polylog(n)-competitive algorithm for metrical task systems. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 711-719, El Paso, Texas, 4-6 May 1997.
- Elias Koutsoupias and Christos Papadimitriou. The 2-evader problem. Information Processing Letters, 57(5):249-252, 11 March 1996.
Selected references
- P. Berman, H. Karloff, and G. Tardos. A competitive 3-server algorithm. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 280-290, San Francisco, California, 22-24 January 1990.
- Avrim Blum, Howard Karloff, Yuval Rabani, and Michael Saks. A decomposition theorem and bounds for randomized server problems. In 33rd Annual Symposium on Foundations of Computer Science, pages 197-207, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.
- Don Coppersmith, Peter Doyle, Prabhakar Raghavan, and Marc Snir. Random walks on weighted graphs and applications to on-line algorithms. Journal of the ACM, 40(3):421-453, July 1993.
- Amos Fiat, Yuval Rabani, and Yiftach Ravid. Competitive k-server algorithms (extended abstract). In 31st Annual Symposium on Foundations of Computer Science, volume II, pages 454-463, St. Louis, Missouri, 22-24 October 1990. IEEE.
- E. F. Grove. The harmonic online K-server algorithm is competitive. In Proceedings of the Twenty Third Annual ACM Symposium on Theory of Computing, pages 260-266, New Orleans, Louisiana, 6-8 May 1991.
- Elias Koutsoupias and Christos H. Papadimitriou. Beyond competitive analysis. In 35th Annual Symposium on Foundations of Computer Science, pages 394-400, Santa Fe, New Mexico, 20-22 November 1994. IEEE.
- Mark S. Manasse, Lyle A. McGeoch, and Daniel D. Sleator. Competitive algorithms for on-line problems. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 322-333, Chicago, Illinois, 2-4 May 1988.
- Daniel D. Sleator and Robert E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202-208, February 1985.