The k-server conjecture is true
Recorded: Sept. 15, 2026, 2:57 p.m.
| Original | Summarized |
[2609.15979] The $k$-server conjecture is true
Skip to main content Search Log in Search arXiv Press Enter to search · Advanced search Computer Science > Data Structures and Algorithms arXiv:2609.15979 (cs) [Submitted on 14 Sep 2026] Abstract: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. Subjects: Data Structures and Algorithms (cs.DS) Cite as: Focus to learn more arXiv-issued DOI via DataCite (pending registration) Submission history From: Marek Zbysiński [view email] [v1]
Full-text links: View a PDF of the paper titled The $k$-server conjecture is true, by Christian Coester and 2 other authorsView PDFHTML (experimental)TeX Source view license < prev | new Change to browse by: References & Citations NASA ADSGoogle Scholar export BibTeX citation BibTeX formatted citation loading... Data provided by: Bookmark
Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Code, Data and Media Associated with this Article alphaXiv Toggle alphaXiv (What is alphaXiv?) Links to Code Toggle CatalyzeX Code Finder for Papers (What is CatalyzeX?) DagsHub Toggle DagsHub (What is DagsHub?) GotitPub Toggle Gotit.pub (What is GotitPub?) Huggingface Toggle Hugging Face (What is Huggingface?) ScienceCast Toggle ScienceCast (What is ScienceCast?) Demos Demos Replicate Toggle Replicate (What is Replicate?) Spaces Toggle Hugging Face Spaces (What is Spaces?) Spaces Toggle TXYZ.AI (What is TXYZ.AI?) Related Papers Recommenders and Search Tools Link to Influence Flower Influence Flower (What are Influence Flowers?) Core recommender toggle CORE Recommender (What is CORE?) Author About arXivLabs arXivLabs: experimental projects with community collaborators Which authors of this paper are endorsers? | We gratefully acknowledge support from About Major funding support from |
The authors prove the $k$-server conjecture, which posits that a deterministic online algorithm can achieve a competitive ratio of $k$ across every metric space. Their proof is achieved by demonstrating that the work function algorithm satisfies this conjecture. The core of their proof relies on establishing a natural algebraic representation for the work function, utilizing a matrix structure to encode all feasible paths to any given configuration. Within this matrix representation, the operations defining optimal costs, specifically minimum and addition, are modeled by matrix addition and multiplication of formal expressions. Furthermore, each work function value is directly captured by the determinant of $k$ columns of this matrix. The process of handling request arrivals is incorporated into this algebraic framework by updating the representation through a change of basis and row replacement operations. The analysis of the performance is conducted using an amortized analysis built upon a potential function defined over a larger matrix, which contains the coordinates of the original matrix representation. This method provides a complex algebraic approach to analyzing the competitive ratios associated with the online scheduling problem. |