The k-Server Conjecture for General Metric Spaces
For every integer k >= 1 and every metric space, prove that there is a deterministic online k-server algorithm whose movement cost on every request sequence is at most k times the offline optimum, up to an additive constant.
Status Open Status review date not recorded in this edition
Listed by ProofAtlas. Status qualification is attributed to ProofAtlas; no full resolution is certified here.
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 2
Claimed by OpenAI. For k >= 2 on arbitrary metrics with at least k+1 points, the manuscript claims a randomized online k-server policy with factor C*(log(k+1))^2 against oblivious finite sequences, plus an additive constant independent of sequence length. Infinite and unbounded metrics are allowed; efficiency is not promised. This is related randomized progress, not the page’s deterministic k-competitive conjecture.See full solution
GitHub repository: https://github.com/openai/math
- OpenAI-110-01-Squared-logarithmic-randomized-k-server-on-arbitrary-metrics.pdfOpen
Claimed by OpenAI. For finite rational metrics and 2 <= k < n, claims a randomized k-server algorithm with O(log^2(k+1)) competitiveness against oblivious requests. Preprocessing is polynomial in input length L; request t costs polynomial in L+log(t+1). The sequence-independent additive constant is not bounded, and activation may be enormously delayed. This is related randomized progress, not the page’s deterministic k-competitive guarantee.See full solution
GitHub repository: https://github.com/openai/math
- OpenAI-110-02-Uniform-computation-of-the-squared-logarithmic-k-server-bound.pdfOpen