Preprint
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 > 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.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- SoK: Fair Clustering: Critique, Caveats, and Future Directions2025
- Exploring fairness in food delivery routing and scheduling problemsExpert Systems with Applications, 2023
- Online k-taxi via Double Coverage and time-reverse primal-dualMathematical Programming, 2022
- On the advice complexity of the k-server problemJournal of Computer and System Sciences, 2017
- On the Advice Complexity of the k-server Problem Under Sparse MetricsTheory of Computing Systems, 2015
- On Online Algorithms with Advice for the k-Server ProblemTheory of Computing Systems, 2012
- On the competitive ratio of the work function algorithm for the k-server problemTheoretical Computer Science, 2004
- An optimal on-line algorithm for metrical task systemJournal of the ACM, 1992
- An Optimal On-Line Algorithm for K Servers on TreesSIAM Journal on Computing, 1991
- Competitive algorithms for server problemsJournal of Algorithms, 1990