LIPIcs.ESA.2021.9.pdf
- Filesize: 0.64 MB
- 11 pages
Document
The Randomized Competitive Ratio of Weighted k-Server Is at Least Exponential
Authors
-
Part of:
Volume:
29th Annual European Symposium on Algorithms (ESA 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-08-31
Cite AsGet BibTex
Nikhil Ayyadevara and Ashish Chiplunkar. The Randomized Competitive Ratio of Weighted k-Server Is at Least Exponential. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 9:1-9:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.9
https://doi.org/10.4230/LIPIcs.ESA.2021.9
Abstract
The weighted k-server problem is a natural generalization of the k-server problem in which the cost incurred in moving a server is the distance traveled times the weight of the server. Even after almost three decades since the seminal work of Fiat and Ricklin (1994), the competitive ratio of this problem remains poorly understood even on the simplest class of metric spaces - the uniform metric spaces. In particular, in the case of randomized algorithms against the oblivious adversary, neither a better upper bound that the doubly exponential deterministic upper bound, nor a better lower bound than the logarithmic lower bound of unweighted k-server, is known. In this paper, we make significant progress towards understanding the randomized competitive ratio of weighted k-server on uniform metrics. We cut down the triply exponential gap between the upper and lower bound to a singly exponential gap by proving that the competitive ratio is at least exponential in k, substantially improving on the previously known lower bound of about ln k.
Subject Classification
ACM Subject Classification
- Theory of computation → Online algorithms
Keywords
- weighted k-server
- competitive analysis
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Dimitris Achlioptas, Marek Chrobak, and John Noga. Competitive analysis of randomized paging algorithms. Theor. Comput. Sci., 234(1-2):203-218, 2000. URL: https://doi.org/10.1016/S0304-3975(98)00116-9.
- Nikhil Bansal, Marek Eliás, and Grigorios Koumoutsos. Weighted k-server bounds via combinatorial dichotomies. In FOCS, pages 493-504, 2017. URL: https://doi.org/10.1109/FOCS.2017.52.
- Nikhil Bansal, Marek Eliás, Grigorios Koumoutsos, and Jesper Nederlof. Competitive algorithms for generalized k-server in uniform metrics. In SODA, pages 992-1001, 2018. URL: https://doi.org/10.1137/1.9781611975031.64.
- Marcin Bienkowski, Łukasz Jeż, and Pawel Schmidt. Slaying hydrae: Improved bounds for generalized k-server in uniform metrics. In ISAAC, volume 149 of LIPIcs, pages 14:1-14:14, 2019. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2019.14.
- Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and Aleksander Madry. k-server via multiscale entropic regularization. In STOC, pages 3-16, 2018. URL: https://doi.org/10.1145/3188745.3188798.
- Ashish Chiplunkar and Sundar Vishwanathan. Randomized memoryless algorithms for the weighted and the generalized k-server problems. ACM Trans. Algorithms, 16(1):14:1-14:28, 2020. URL: https://doi.org/10.1145/3365002.
- Marek Chrobak and Jiří Sgall. The weighted 2-server problem. Theoretical Computer Science, 324(2-3):289-312, 2004. URL: https://doi.org/10.1016/j.tcs.2004.05.020.
- Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel Dominic Sleator, and Neal E. Young. Competitive paging algorithms. J. Algorithms, 12(4):685-699, 1991. URL: https://doi.org/10.1016/0196-6774(91)90041-V.
- Amos Fiat and Moty Ricklin. Competitive algorithms for the weighted server problem. Theoretical Computer Science, 130(1):85-99, 1994. URL: https://doi.org/10.1016/0304-3975(94)90154-6.
- Elias Koutsoupias and Christos H. Papadimitriou. On the k-server conjecture. J. ACM, 42(5):971-983, 1995. URL: https://doi.org/10.1145/210118.210128.
- James R. Lee. Fusible HSTs and the randomized k-server conjecture. In FOCS, pages 438-449, 2018. URL: https://doi.org/10.1109/FOCS.2018.00049.
- Mark S. Manasse, Lyle A. McGeoch, and Daniel Dominic Sleator. Competitive algorithms for on-line problems. In STOC, pages 322-333, 1988. URL: https://doi.org/10.1145/62212.62243.
- Lyle A. McGeoch and Daniel Dominic Sleator. A strongly competitive randomized paging algorithm. Algorithmica, 6(6):816-825, 1991. URL: https://doi.org/10.1007/BF01759073.
- René Sitters. The generalized work function algorithm is competitive for the generalized 2-server problem. SIAM J. Comput., 43(1):96-125, 2014. URL: https://doi.org/10.1137/120885309.
- Neal E. Young. On-line file caching. Algorithmica, 33(3):371-383, 2002. URL: https://doi.org/10.1007/s00453-001-0124-5.