Metraipolis › archive › dc_a874ffa78dbe
The $k$-server conjecture is true — arXiv:2609.15979
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.15979
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T02:15:39.098Z
- SHA-256 of the archived text
575b5cfb954ccb49280fdff5ea97426231e84008d4458af40ab2ef0f3802f416- Stable URL of this page
https://metraipolis.com/documento/dc_a874ffa78dbe
How to cite
The $k$-server conjecture is true — arXiv:2609.15979 — arXiv (en), https://arxiv.org/abs/2609.15979 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a874ffa78dbe (Metraipolis archive dc_a874ffa78dbe, sha256 575b5cfb954ccb49280fdff5ea97426231e84008d4458af40ab2ef0f3802f416)
BibTeX
@misc{dca874ffa78dbe,
title = {The $k$-server conjecture is true — arXiv:2609.15979},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.15979},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a874ffa78dbe; sha256 575b5cfb954ccb49280fdff5ea97426231e84008d4458af40ab2ef0f3802f416},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.15979. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The $k$-server conjecture states that a deterministic online algorithm can achieve competitive ratio $k$ on every metric space. We prove the conjecture. Specifically, we show that the work function algorithm satisfies it. Our proof uses a natural algebraic representation of the work function as a matrix, which encodes all feasible paths to reach a configuration. In this representation, the minimum and addition operations arising in the definition of optimal costs correspond to addition and multiplication of formal expressions, and each work function value corresponds to the determinant of $k$ columns of the matrix. A request arrival updates the representation via a change of basis and row replacement. The amortized analysis is based on a potential function defined in terms of a larger matrix whose coordinates are pairs of coordinates of the original matrix representation. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-15 in cs.DS). Categorie arXiv: Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2609.15979 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T01:54:07.139Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).