{"ID":2825383,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.20960","arxiv_id":"2512.20960","title":"Fairness in the k-Server Problem","abstract":"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 $α\\ge 1$ and $β\\ge 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 $\\varepsilon \u003e 0$, transforms any optimal solution into an $(α,β)$-fair solution for $α= 1 + \\varepsilon$ and $β= O(\\mathrm{diam} \\cdot \\log k / \\varepsilon)$, while increasing the cost of the solution by just an additive $O(\\mathrm{diam} \\cdot k \\log k / \\varepsilon)$ term. Here $\\mathrm{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.","short_abstract":"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 $α\\ge 1$ and $β\\ge 0$, no server incurs more than a...","url_abs":"https://arxiv.org/abs/2512.20960","url_pdf":"https://arxiv.org/pdf/2512.20960v1","authors":"[\"Mohammadreza Daneshvaramoli\",\"Helia Karisani\",\"Mohammad Hajiesmaili\",\"Shahin Kamali\",\"Cameron Musco\"]","published":"2025-12-24T05:33:35Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\"]","methods":"[]","has_code":false}