Document Open Access Logo

Towards the k-Server Conjecture: A Unifying Potential, Pushing the Frontier to the Circle

Authors Christian Coester, Elias Koutsoupias

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.57.pdf
  • Filesize: 0.72 MB
  • 20 pages

Document Identifiers

Author Details

Christian Coester
  • CWI, Amsterdam, The Netherlands
Elias Koutsoupias
  • University of Oxford, UK

Funding

  • Coester, Christian: Supported by NWO VICI grant 639.023.812.

Cite AsGet BibTex

Christian Coester and Elias Koutsoupias. Towards the k-Server Conjecture: A Unifying Potential, Pushing the Frontier to the Circle. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 57:1-57:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.57

Abstract

The k-server conjecture, first posed by Manasse, McGeoch and Sleator in 1988, states that a k-competitive deterministic algorithm for the k-server problem exists. It is conjectured that the work function algorithm (WFA) achieves this guarantee, a multi-purpose algorithm with applications to various online problems. This has been shown for several special cases: k = 2, (k+1)-point metrics, (k+2)-point metrics, the line metric, weighted star metrics, and k = 3 in the Manhattan plane. The known proofs of these results are based on potential functions tied to each particular special case, thus requiring six different potential functions for the six cases. We present a single potential function proving k-competitiveness of WFA for all these cases. We also use this potential to show k-competitiveness of WFA on multiray spaces and for k = 3 on trees. While the DoubleCoverage algorithm was known to be k-competitive for these latter cases, it has been open for WFA. Our potential captures a type of lazy adversary and thus shows that in all settled cases, the worst-case adversary is lazy. Chrobak and Larmore conjectured in 1992 that a potential capturing the lazy adversary would resolve the k-server conjecture. To our major surprise, this is not the case, as we show (using connections to the k-taxi problem) that our potential fails for three servers on the circle. Thus, our potential highlights laziness of the adversary as a fundamental property that is shared by all settled cases but violated in general. On the one hand, this weakens our confidence in the validity of the k-server conjecture. On the other hand, if the k-server conjecture holds, then we believe it can be proved by a variant of our potential.

Subject Classification

ACM Subject Classification
  • Theory of computation → K-server algorithms
Keywords
  • Online algorithms
  • competitive analysis
  • k-server
  • work function algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. C. J. Argue, Anupam Gupta, Guru Guruganesh, and Ziye Tang. Chasing convex bodies with linear competitive ratio. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA '20, pages 1519-1524, 2020. Google Scholar
  2. Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Joseph Naor. A polylogarithmic-competitive algorithm for the k-server problem. J. ACM, 62(5):40:1-40:49, 2015. Google Scholar
  3. Nikhil Bansal, Marek Eliás, and Grigorios Koumoutsos. Weighted k-server bounds via combinatorial dichotomies. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS '17, 2017. Google Scholar
  4. Yair Bartal and Elias Koutsoupias. On the competitive ratio of the work function algorithm for the k-server problem. Theoretical Computer Science, 324(2-3):337-345, 2004. Google Scholar
  5. Wolfgang W. Bein, Marek Chrobak, and Lawrence L. Larmore. The 3-server problem in the plane. Theor. Comput. Sci., 289(1):335-354, 2002. Google Scholar
  6. Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press, 1998. Google Scholar
  7. Allan Borodin, Nathan Linial, and Michael E. Saks. An optimal on-line algorithm for metrical task system. J. ACM, 39(4):745-763, 1992. Google Scholar
  8. Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and Aleksander Madry. k-server via multiscale entropic regularization. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 3-16, 2018. Google Scholar
  9. William R. Burley. Traversing layered graphs using the work function algorithm. J. Algorithms, 20(3):479-511, 1996. Google Scholar
  10. Marek Chrobak, Howard Karloff, Tom Payne, and Sundar Vishwanathan. New results on server problems. SIAM Journal on Discrete Mathematics, 4(2):172-181, 1991. Google Scholar
  11. Marek Chrobak and Lawrence L. Larmore. An optimal on-line algorithm for k servers on trees. SIAM Journal on Computing, 20(1):144-148, 1991. Google Scholar
  12. Marek Chrobak and Lawrence L Larmore. The server problem and on-line games. In On-line Algorithms, volume 7 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. Citeseer, 1992. Google Scholar
  13. Christian Coester and Elias Koutsoupias. The online k-taxi problem. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC '19, 2019. Google Scholar
  14. Christian Coester and Elias Koutsoupias. Towards the k-server conjecture: A unifying potential, pushing the frontier to the circle. CoRR, abs/2102.10474, 2021. URL: http://arxiv.org/abs/2102.10474.
  15. Andreas W.M. Dress and Walter Wenzel. Valuated matroids: a new look at the greedy algorithm. Applied Mathematics Letters, 3(2):33-35, 1990. Google Scholar
  16. Amos Fiat, Yuval Rabani, and Yiftach Ravid. Competitive k-server algorithms. J. Comput. Syst. Sci., 48(3), 1994. Google Scholar
  17. Alexander S. Kelso Jr and Vincent P. Crawford. Job matching, coalition formation, and gross substitutes. Econometrica: Journal of the Econometric Society, pages 1483-1504, 1982. Google Scholar
  18. Elias Koutsoupias. Weak adversaries for the k-server problem. In 40th Annual Symposium on Foundations of Computer Science, FOCS '99, pages 444-449, 1999. Google Scholar
  19. Elias Koutsoupias. The k-server problem. Computer Science Review, 3(2):105-118, 2009. Google Scholar
  20. Elias Koutsoupias and Christos Papadimitriou. The 2-evader problem. Information Processing Letters, 57(5):249-252, 1996. Google Scholar
  21. Elias Koutsoupias and Christos H. Papadimitriou. On the k-server conjecture. J. ACM, 42(5), 1995. Google Scholar
  22. James R. Lee. Fusible HSTs and the randomized k-server conjecture. In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS '18, pages 438-449, 2018. Google Scholar
  23. Mark S. Manasse, Lyle A. McGeoch, and Daniel Dominic Sleator. Competitive algorithms for on-line problems. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC '88, 1988. Google Scholar
  24. Kazuo Murota. Discrete Convex Analysis. Society for Industrial and Applied Mathematics, January 2003. Google Scholar
  25. Mark Sellke. Chasing convex bodies optimally. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA '20, pages 1509-1518, 2020. Google Scholar
  26. René Sitters. The generalized work function algorithm is competitive for the generalized 2-server problem. SIAM J. Comput., 43(1), 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact