License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2022.30
URN: urn:nbn:de:0030-drops-161906
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16190/
Raghvendra, Sharath ;
Sowle, Rachita
A Scalable Work Function Algorithm for the k-Server Problem
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.
BibTeX - Entry
@InProceedings{raghvendra_et_al:LIPIcs.SWAT.2022.30,
author = {Raghvendra, Sharath and Sowle, Rachita},
title = {{A Scalable Work Function Algorithm for the k-Server Problem}},
booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
pages = {30:1--30:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-236-5},
ISSN = {1868-8969},
year = {2022},
volume = {227},
editor = {Czumaj, Artur and Xin, Qin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16190},
URN = {urn:nbn:de:0030-drops-161906},
doi = {10.4230/LIPIcs.SWAT.2022.30},
annote = {Keywords: k-server, Work Function Algorithm, Minimum-cost Flow}
}
