On the k-server conjecture

ABSTRACT

We prove that the work function algorithm for the k-server problem has a competitive ratio at most 2k−1. Manasse et al. [1988] 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 configuration that achieve maximum increase of the work function, and a potential function that exploits the duality lemma.

REFERENCES

• 1: ~BEN-DAVID, S., BORODIN, A., KARP, R., TARDOS, G., AND WIGDERSON, A. 1994. On the power ~of randomization in on-line algorithms. Algorlthmzca 11, 1 (Jan.), 2-14.
• 2: 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
• 3: ~BLUM, A., KARLOFF, H., RABANI, Y., AND SAKS, M. 1992. A decomposition theorem and ~bounds for randomized server problems. In Proceedings of the 33rd Annual Symposium on ~Foundations of Computer Science. IEEE, New York, pp. 197-207.
• 4: ~BURLEY, W.R. 1993. Traversing layered graphs using the work function algorithm. Tech. Rep. ~CS93-319. Dept. of Computer Science and Engineering. Unw. of Cahfornia at San Diego, San ~Diego, Calif.
• 5: M. Chrobak , H. Karloff , T. Payne , S. Vishwanathan, New results on server problems, SIAM Journal on Discrete Mathematics, v.4 n.2, p.172-181, May 1991 [doi>10.1137/0404017]
• 6: Marek Chrobak , Lawrence L. Larmore, An optimal on-line algorithm for K-servers on trees, SIAM Journal on Computing, v.20 n.1, p.144-148, Feb. 1991 [doi>10.1137/0220008]
• 7: Marek Chrobak , Lawrence L. Larmore, On fast algorithms for two servers, Journal of Algorithms, v.12 n.4, p.607-614, Dec. 1991 [doi>10.1016/0196-6774(91)90035-W]
• 8: Marek Chrobak , Lawrence L. Larmore, HARMONIC is a 3–competitive for two servers, Theoretical Computer Science, v.98 n.2, p.339-346, 18 May 1992 [doi>10.1016/0304-3975(92)90007-3]
• 9: ~CHROBAK, M., AND LARMORE, L.L. 1992b. The server problem and ondme games. In On-Line ~Algolfthms: Proceedings of a DIMACS Workshop. DIMACS Series in Discrete Mathematics and ~Theoretical Computer Science, vol. 7. ACM, New York, pp. 11-64.
• 10: Marek Chrobak , Lawrence L. Larmore, Generosity helps or an 11-competitive algorithm for three servers, Journal of Algorithms, v.16 n.2, p.234-263, March 1994 [doi>10.1006/jagm.1994.1011]
• 11: Marek Chrobak , Lawrence L. Larmore , Nick Reingold , Jeffery Westbrook, Page Migration Algorithms Using Work Functions, Proceedings of the 4th International Symposium on Algorithms and Computation, p.406-415, December 15-17, 1993
• 12: Don Coppersmith , Peter Doyle , Prabhakar Raghavan , Marc Snir, Random walks on weighted graphs and applications to on-line algorithms, Journal of the ACM (JACM), v.40 n.3, p.421-453, July 1993 [doi>10.1145/174130.174131]
• 13: ~FIAT, A., RABANI, Y., AND RAVID, Y. 1990. Competitive k-server algorithms. In Proceedltzgs of ~the 31st Annual Symposium on Foundations of Computer Science. vol. 2. IEEE, New York, ~pp. 454 463.
• 14: ~FIAT, A., RABANI, Y., RAVID, Y., AND 8CHIEBER, B. 1994. A deterministic O(k3)-competitive ~k-server algorithm for the circle. Algonthmiea 11, 6 (June), 572-578.
• 15: 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 [doi>10.1145/103418.103448]
• 16: Sandy Irani , Ronitt Rubinfeld, A competitive 2-server algorithm, Information Processing Letters, v.39 n.2, p.85-91, July 31, 1991 [doi>10.1016/0020-0190(91)90160-J]
• 17: ~KARLIN, A. R., MANASSE, M. S., McGEOCH, L. A., AND OWtCKI, S. 1994. Competitive random- ~ized algorithms for nonuniform problems. Algorithmica 11, 6 (June), 542-571.
• 18: Howard Karloff , Yuval Rabani , Yiftach Ravid, Lower Bounds for Randomized $k$-Serverand Motion-Planning Algorithms, SIAM Journal on Computing, v.23 n.2, p.293-312, April 1994 [doi>10.1137/S0097539792224838]
• 19: Elias Koutsoupias, On-line algorithms and the K-server conjecture, University of California at San Diego, La Jolla, CA, 1995
• 20: Elias Koutsoupias , Christos Papadimitriou, On the k-server conjecture, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.507-511, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195245]
• 21: KOUTSOUPIAS, E., AND PAPADIMITRIOU, C.H. The 2-evader problem. In preparation.
• 22: KOUTSOUPIAS, E., AND PAPADIM1TRIOU, C.H. 1994. Beyond competitive analysis. In Proceed- ~ings of the 35th IEEE Symposium on Foundations of Comptttet' Sicience (FOCS). IEEE, New ~York, 394-400.
• 23: 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]
• 24: 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]
• 25: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Performance, Theory

Keywords:
k-server problem, competitive analysis, online algorithms, potential, quasiconvexity, work function