Deterministic $k$-server conjecture

The paper proves the work function algorithm (WFA) is $k$-competitive for the $k$-server problem on every metric space. Specifically, for initial configuration $C_0$ and every finite request sequence $\sigma$, $$\mathrm{WFA}_{C_0}(\sigma)\leq k\,\mathrm{OPT}_{C_0}(\sigma)+\mathrm{cl}(C_0).$$ Since a competitive ratio below $k$ is impossible in general, this settles the deterministic $k$-server conjecture with the optimal ratio. The proof represents work-function values as valuations of determinants over a formal field and constructs a potential from quadratic products of the determinant columns. Its increase at each request pays the extended cost of WFA, yielding the global bound. This does not concern the separate randomized $k$-server conjecture, which was previously refuted.

The paper proves the work function algorithm (WFA) is $k$-competitive for the $k$-server problem on every metric space. Specifically, for initial configuration $C_0$ and every finite request sequence $\sigma$, $$\mathrm{WFA}_{C_0}(\sigma)\leq k\,\mathrm{OPT}_{C_0}(\sigma)+\mathrm{cl}(C_0).$$ Since a competitive ratio below $k$ is impossible in general, this settles the deterministic $k$-server conjecture with the optimal ratio. The proof represents work-function values as valuations of determinants over a formal field and constructs a potential from quadratic products of the determinant columns. Its increase at each request pays the extended cost of WFA, yielding the global bound. This does not concern the separate randomized $k$-server conjecture, which was previously refuted.