Coester, Koutsoupias, Zbysiński prove k-server conjecture

"The k-server conjecture states that a deterministic online algorithm can achieve competitive ratio k on every metric space. We prove the conjecture." That is the abstract's opening of the arxiv preprint by Christian Coester, Elias Koutsoupias, and Marek Zbysiński.

The problem has been open since Manasse, McGeoch and Sleator introduced it in 1988. The paper calls it the "holy grail" of competitive analysis. Koutsoupias, with Papadimitriou, had previously shown that the work function algorithm, the same algorithm the new proof analyses, achieves a competitive ratio of 2k-1 on general metrics; the conjectured k bound had otherwise been confirmed only in restricted settings such as k=2, metrics with k+1 or k+2 points, line metrics, weighted stars, trees, and circles.

"Specifically, we show that the work function algorithm satisfies it," the abstract adds. The proof introduces an algebraic representation in which each work function value corresponds to the determinant of k columns of a matrix, and the amortized analysis rests on a potential function built from quadratic products of those vectors.

Two researchers on our Who's Who list had already shared the link by the time it reached our radar.