Math Conjectures

k-Server Conjecture

OPENLandmarkConjectureProposed 1988 · Full conjecture

Canonical statement

For every kk and every metric space, there is a deterministic online algorithm for the kk-server problem whose movement cost on every finite request sequence is at most kk times the offline optimum plus an additive constant independent of the request sequence.
View source LaTeX
For every \(k\) and every metric space, there is a deterministic online algorithm for the \(k\)-server problem whose movement cost on every finite request sequence is at most \(k\) times the offline optimum plus an additive constant independent of the request sequence.
TCS-ONLINE-031:[ManasseMcGeochSleator1990Online][KoutsoupiasPapadimitriou1995KServer][BorodinElYaniv1998Online]
Theoretical computer scienceOperations research

Notes

In the k-server problem, k mobile servers occupy points of a metric space and must serve an online request sequence by moving a server to each requested point, paying total distance moved. Manasse, McGeoch, and Sleator conjectured that a deterministic online algorithm can always achieve competitive ratio k, matching the universal lower bound [ManasseMcGeochSleator1990Online].

The work-function algorithm gives the best general deterministic guarantee, 2k−1, proved by Koutsoupias and Papadimitriou [KoutsoupiasPapadimitriou1995KServer]; the framework and special-metric results are surveyed by Borodin and El-Yaniv [BorodinElYaniv1998Online]. No deterministic algorithm achieves ratio k on every metric, and no lower bound above k refutes the conjecture. Randomized algorithms and improvements for lines, trees, or other structured metrics concern different versions.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.