2026-07-24T06:07:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14126 2024-03-06T10:53:32Z ddc:004 open_access

Towards the k-Server Conjecture: A Unifying Potential, Pushing the Frontier to the Circle Coester, Christian Koutsoupias, Elias Online algorithms competitive analysis k-server work function algorithm 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christian Coester and Elias Koutsoupias 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.57 urn:nbn:de:0030-drops-141263 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.57 eng https://creativecommons.org/licenses/by/4.0/legalcode