Long-Standing k-Server Conjecture Proved via Work Function Algorithm
The paper proves the decades-old k-server conjecture, showing that the classical work function algorithm achieves the optimal competitive ratio k on every metric space. The authors' approach represents the work function algebraically as a matrix encoding all feasible paths to a configuration, so that computing optimal costs corresponds to matrix operations and work function values become determinants; request updates are handled via change of basis, with the amortized analysis built on a potential function over pairs of matrix coordinates. Twitter commentary frames this as part of a remarkable recent wave of resolved open problems in online algorithms and combinatorics, with one researcher (linked to the related Matroid Secretary breakthrough) noting a long-conjectured 1/4-competitive guarantee was similarly just proved, and others simply marveling at how many longstanding conjectures are falling in quick succession.
Discussion: 2 tweets from 2 authors · @Aaroth, @sahilsingla81