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/
Go to the corresponding LIPIcs Volume Portal


Raghvendra, Sharath ; Sowle, Rachita

A Scalable Work Function Algorithm for the k-Server Problem

pdf-format:
LIPIcs-SWAT-2022-30.pdf (0.9 MB)


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}
}

Keywords: k-server, Work Function Algorithm, Minimum-cost Flow
Collection: 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Issue Date: 2022
Date of publication: 22.06.2022
Supplementary Material: Software (Source Code): https://github.com/RachitaS/ScalableWorkFunction_Public archived at: https://archive.softwareheritage.org/swh:1:dir:892a63bde62da09de7b9fb9b2086263cd9f8980b


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI