← All problems

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.

Source: Huang and Zhang, Deterministic 3-Server on a Circle and the Limitation of Canonical Potentials, abstract (2022).

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.

References

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 solutionHide full solution
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 solutionHide full solution