LIPIcs.SWAT.2022.30.pdf
- Filesize: 0.88 MB
- 20 pages
Document
A Scalable Work Function Algorithm for the k-Server Problem
Authors
-
Part of:
Volume:
18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-06-22
Cite As Get BibTex
Sharath Raghvendra and Rachita Sowle. A Scalable Work Function Algorithm for the k-Server Problem. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 30:1-30:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SWAT.2022.30
Abstract
We provide a novel implementation of the classical Work Function Algorithm (WFA) for the k-server problem. In our implementation, processing a request takes O(n²+k²) time per request; where n is the total number of requests and k is the total number of servers. All prior implementations take Ω(kn² +k³) time per request. Previous approaches process a request by solving a min-cost flow problem. Instead, we show that processing a request can be reduced to an execution of the Dijkstra’s shortest-path algorithm on a carefully computed weighted graph leading to the speed-up.
Subject Classification
ACM Subject Classification
- Theory of computation → K-server algorithms
Keywords
- k-server
- Work Function Algorithm
- Minimum-cost Flow
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
Supplementary Materials
-
Software (Source Code)
https://github.com/RachitaS/ScalableWorkFunction_Public
browse
archived version
References
- Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and Aleksander Madry. k-server via multiscale entropic regularization. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 3-16. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188798.
- Marek Chrobak, Howard J. Karloff, T. H. Payne, and Sundar Vishwanathan. New results on server problems. SIAM J. Discret. Math., 4(2):172-181, 1991. URL: https://doi.org/10.1137/0404017.
- Marek Chrobak and Lawrence L. Larmore. An optimal on-line algorithm for k-servers on trees. SIAM J. Comput., 20(1):144-148, 1991. URL: https://doi.org/10.1137/0220008.
- Donald B. Johnson. Efficient algorithms for shortest paths in sparse networks. J. ACM, 24(1):1-13, 1977. URL: https://doi.org/10.1145/321992.321993.
- B. Kalyanasundaram and K. Pruhs. Online weighted matching. Journal of Algorithms, 14(3):478-488, 1993. URL: https://doi.org/10.1006/jagm.1993.1026.
- Samir Khuller, Stephen G. Mitchell, and Vijay V. Vazirani. On-line algorithms for weighted bipartite matching and stable marriages. Theor. Comput. Sci., 127(2):255-267, 1994. URL: https://doi.org/10.1016/0304-3975(94)90042-6.
- Elias Koutsoupias. The k-server problem. Comput. Sci. Rev., 3(2):105-118, 2009. URL: https://doi.org/10.1016/j.cosrev.2009.04.002.
- 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.
- Harold W. Kuhn. The hungarian method for the assignment problem. In Michael Jünger, Thomas M. Liebling, Denis Naddef, George L. Nemhauser, William R. Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, and Laurence A. Wolsey, editors, 50 Years of Integer Programming 1958-2008 - From the Early Years to the State-of-the-Art, pages 29-47. Springer, 2010. URL: https://doi.org/10.1007/978-3-540-68279-0_2.
- James R. Lee. Fusible hsts and the randomized k-server conjecture. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 438-449. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00049.
- Mark S. Manasse, Lyle A. McGeoch, and Daniel Dominic Sleator. Competitive algorithms for server problems. J. Algorithms, 11(2):208-230, 1990. URL: https://doi.org/10.1016/0196-6774(90)90003-W.
- Krati Nayyar and Sharath Raghvendra. An input sensitive online algorithm for the metric bipartite matching problem. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 505-515. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.53.
- Sharath Raghvendra. A robust and optimal online algorithm for minimum metric bipartite matching. In Klaus Jansen, Claire Mathieu, José D. P. Rolim, and Chris Umans, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, September 7-9, 2016, Paris, France, volume 60 of LIPIcs, pages 18:1-18:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.18.
- Sharath Raghvendra. Optimal analysis of an online algorithm for the bipartite matching problem on a line. In Bettina Speckmann and Csaba D. Tóth, editors, 34th International Symposium on Computational Geometry, SoCG 2018, June 11-14, 2018, Budapest, Hungary, volume 99 of LIPIcs, pages 67:1-67:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.SoCG.2018.67.
- Tomislav Rudec, Alfonzo Baumgartner, and Robert Manger. A fast work function algorithm for solving the k-server problem. Central Eur. J. Oper. Res., 21(1):187-205, 2013. URL: https://doi.org/10.1007/s10100-011-0222-7.
-
Tomislav Rudec, Alfonzo Baumgartner, and Robert Manger. A fast work function algorithm for solving the k-server problem. Central European Journal of Operations Research, 21:187-205, 2013.
- Tomislav Rudec and Robert Manger. A new approach to solve the k-server problem based on network flows and flow cost reduction. Comput. Oper. Res., 40(4):1004-1013, 2013. URL: https://doi.org/10.1016/j.cor.2012.11.006.