arXiv preprint claims proof of the k-server conjecture via the work function algorithm

What was claimed

A preprint posted to arXiv claims to resolve the k-server conjecture, one of the longest-standing open problems in theoretical computer science. The paper, deposited on 14 September 2026 according to its arXiv submission history, which lists Marek Zbysinski as the submitter, reached a wider audience the next day when it appeared on the front page of Hacker News. According to the paper's abstract, the author proves the conjecture by showing that the work function algorithm, a strategy studied for more than three decades, achieves a competitive ratio of k on every metric space.

The problem

In the k-server problem, k servers occupy points of a metric space. Requests arrive one at a time, and the algorithm must move one of its servers to the requested point, paying a cost equal to the distance travelled. The algorithm learns each request only when it arrives, yet its performance is judged against an offline optimum that knows the entire request sequence in advance. The ratio between the algorithm's total cost and that optimum is its competitive ratio.

The conjecture, formulated by Mark Manasse, Lyle McGeoch and Daniel Sleator in the late 1980s, holds that a deterministic online algorithm can be k-competitive on every metric space. That target is tight, since no deterministic algorithm can beat a factor of k in general. For many years the best known general bound was 2k-1, established for the work function algorithm by Elias Koutsoupias and Christos Papadimitriou. Special metric spaces, including uniform spaces, trees and lines, admitted k-competitive algorithms, but the general statement stayed open.

How the proof works

The argument is algebraic. According to the abstract, the paper represents the work function as a matrix that encodes all feasible paths for reaching a given configuration of servers. In this representation, the minimum and addition operations that arise in the definition of optimal costs correspond to addition and multiplication of formal expressions, and every work function value corresponds to the determinant of k columns of the matrix. The arrival of a new request updates the representation through a change of basis combined with a row replacement. The competitive bound itself comes from an amortized analysis built on a potential function defined over a larger matrix whose coordinates are pairs of coordinates from the original representation.

The translation between min-plus operations and ordinary arithmetic is reminiscent of tropical algebra, and the overall shape of the proof is a recasting of combinatorial bookkeeping as linear algebra, which appears to be what makes the analysis tractable.

What happens next

For now the claim exists as a 22 KB preprint, and like any proposed resolution of a major conjecture it will have to survive close review. Competitive analysis is dense with boundary cases, and each piece of the new machinery, from the matrix representation to the determinant reading of work function values and the pair-coordinate potential function, will need independent checking. Front-page placement on Hacker News signals attention rather than endorsement, and a technical verdict is likely to take longer than a news cycle.

Why it matters

If verified, the result closes a question that has helped define online algorithms as a field since the late 1980s. The k-server problem is a deliberately clean model of something ubiquitous: keeping a fixed set of resources positioned to serve demand you cannot foresee. Paging and caching are the canonical special case, obtained when the metric space is uniform, and the same structure abstracts the allocation of machines, vehicles or repair crews. A proof that the work function algorithm is k-competitive would confirm that a simple, deterministic, long-known rule is worst-case optimal, matching the lower bound of k exactly rather than leaving a gap that grows with the number of servers.

The technique may matter as much as the theorem. Recasting the work function as linear algebra, with requests acting as basis changes and costs read off determinants, is the kind of structural move that tends to migrate to neighbouring problems, such as metrical task systems and randomized variants of k-server, where substantial gaps between known upper and lower bounds remain.