Generosity helps, or an 11–competitive algorithm for three servers

ABSTRACT

We propose a new algorithm called Equipoise for the k-server problem, and we prove that it is 2-competitive for two servers and 11-competitive for three servers. For k=3, this is a tremendous improvement over previously known constants. The algorithm uses several techniques for designing on-line algorithms - convex hulls, work functions and forgiveness. The results presented in this paper were earlier announced at the DIMACS Workshop on On-Line Algorithms [8].

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: 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: 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]
• 4: M. Chrobak and L. Larmore. Harmonic is threecompetitive for two servers. Submitted for ~ublication.
• 5: M. Chrobak and L. Larmore. A new approach to the server problem. SIAM Journal on Discrete Mathematics, 1991. To appear.
• 6: 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]
• 7: 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]
• 8: M. Chrobak and L. Larmore. The server problem and on-line games. In Proceedings of DIAMGS Workshop on On-Line Algorithms, 1991. To appear.
• 9: 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 [doi>10.1145/100216.100266]
• 10: A. Fiat, Y. Rabani, and Y. Ravid. Competitive kserver algorithms. In Proc. ~~nd Symposium on Theory o/Algorithms, 1990.
• 11: E. Grove. The harmonic on-line k-server algorithm is competitive. Manuscript.
• 12: S. Irani and R. Rubinfeld. A competitive 2-server algorithm. Manuscript.
• 13: 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]
• 14: Prabhakar Raghavan , Marc Snir, Memory Versus Randomization in On-line Algorithms (Extended Abstract), Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.687-703, July 11-15, 1989

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Theory, Verification