What the conjecture claims

With k servers moving around a metric space to answer requests, a deterministic algorithm with no view of the future should still cost at most k times the best offline plan. On every metric space, no exceptions.

“a deterministic online algorithm can achieve competitive ratio $k$ on every metric space”

Now it is proven

Christian Coester, Elias Koutsoupias and Marek Zbysiński posted the proof to arXiv on 14 September 2026. Three sentences of abstract close a question the field has chased for decades.

“We prove the conjecture.”

The old algorithm wins

No new method was needed. The work function algorithm, long suspected to be the answer, is the one shown to hit ratio k everywhere.

“we show that the work function algorithm satisfies it”

Write it as a matrix

The proof reframes the work function algebraically. A matrix holds every feasible path to reach a given server configuration, so the combinatorics turn into linear algebra.

“a natural algebraic representation of the work function as a matrix, which encodes all feasible paths to reach a configuration”

Costs become determinants

The minimum and addition that define optimal cost map onto addition and multiplication of formal expressions. Each work function value then reads off as the determinant of k columns.

Each request shifts the basis

A new request updates the matrix by a change of basis plus a row replacement. The amortized analysis rides on a potential function built from a larger matrix whose coordinates are pairs of the original ones.