Time-Optimal $k$-Server
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912264644198400 |
|---|---|
| author | Frei, Fabian Komm, Dennis Stocker, Moritz Whittington, Philip |
| author_facet | Frei, Fabian Komm, Dennis Stocker, Moritz Whittington, Philip |
| contents | The time-optimal $k$-server problem minimizes the time spent serving all requests instead of the distances traveled. We give a lower bound of $2k-1$ on the competitive ratio of any deterministic online algorithm for this problem, which coincides with the best known upper bound on the competitive ratio achieved by the work-function algorithm for the classical $k$-server problem. We provide further lower bounds of $k+1$ for all Euclidean spaces and $k$ for uniform metric spaces. For the latter, we give a matching $k$-competitive deterministic algorithm. Our most technical result, proven by applying Yao's principle to a suitable instance distribution on a specifically constructed metric space, is a lower bound of $k+\mathcal{O}(\log k)$ that holds even for randomized algorithms, which contrasts with the best known lower bound for the classical problem that remains polylogarithmic.
With this paper, we hope to initiate a further study of this natural yet neglected problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_05589 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Time-Optimal $k$-Server Frei, Fabian Komm, Dennis Stocker, Moritz Whittington, Philip Data Structures and Algorithms The time-optimal $k$-server problem minimizes the time spent serving all requests instead of the distances traveled. We give a lower bound of $2k-1$ on the competitive ratio of any deterministic online algorithm for this problem, which coincides with the best known upper bound on the competitive ratio achieved by the work-function algorithm for the classical $k$-server problem. We provide further lower bounds of $k+1$ for all Euclidean spaces and $k$ for uniform metric spaces. For the latter, we give a matching $k$-competitive deterministic algorithm. Our most technical result, proven by applying Yao's principle to a suitable instance distribution on a specifically constructed metric space, is a lower bound of $k+\mathcal{O}(\log k)$ that holds even for randomized algorithms, which contrasts with the best known lower bound for the classical problem that remains polylogarithmic. With this paper, we hope to initiate a further study of this natural yet neglected problem. |
| title | Time-Optimal $k$-Server |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.05589 |