2026-10-11T04:21:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25332 2026-03-19T12:03:38Z ddc:004 open_access

Fairness in the k-Server Problem Daneshvaramoli, Mohammadreza Hajiesmaili, Mohammad Kamali, Shahin Karisani, Helia Musco, Cameron k-server problem online algorithms fairness competitive analysis We initiate a formal study of fairness for the k-server problem, where the objective is not only to minimize the total movement cost, but also to distribute the cost equitably among servers. We first define a general notion of (α,β)-fairness, where, for parameters α ≥ 1 and β ≥ 0, no server incurs more than an α/k-fraction of the total cost plus an additive term β. We then show that fairness can be achieved without a loss in competitiveness in both the offline and online settings. In the offline setting, we give a deterministic algorithm that, for any ε > 0, transforms any optimal solution into an (α,β)-fair solution for α = 1 + ε and β = O(diam ⋅ log k / ε), while increasing the cost of the solution by just an additive O(diam ⋅ k log k / ε) term. Here diam is the diameter of the underlying metric space. We give a similar result in the online setting, showing that any competitive algorithm can be transformed into a randomized online algorithm that is fair with high probability against an oblivious adversary and still competitive up to a small loss. The above results leave open a significant question: can fairness be achieved in the online setting, either with a deterministic algorithm or a randomized algorithm, against a fully adaptive adversary? We make progress towards answering this question, showing that the classic deterministic Double Coverage Algorithm (DCA) is fair on line metrics and on tree metrics when k = 2. However, we also show a negative result: DCA fails to be fair for any non-vacuous parameters on general tree metrics. We further show that on uniform metrics (i.e., the paging problem), the deterministic First-In First-Out (FIFO) algorithm is fair. We show that any "marking algorithm", including the Least Recently Used (LRU) algorithm, also satisfies a weaker, but still meaningful notion of fairness. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mohammadreza Daneshvaramoli and Mohammad Hajiesmaili and Shahin Kamali and Helia Karisani and Cameron Musco 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.45 urn:nbn:de:0030-drops-253328 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.45 eng https://creativecommons.org/licenses/by/4.0/legalcode