The k-Server Conjecture

Claim: there exists a deterministic online algorithm using k servers that is k-competitive on every metric space: for every request sequence σ, its total movement cost is at most k times the optimal offline cost OPT(σ).

Formalised by Manasse, McGeoch and Sleator (1990) after folklore interest through the 1980s; the lower bound is exactly k (any metric with k+1 points forces it). The WORK-FUNCTION algorithm achieves 2k−1 competitiveness (Koutsoupias–Papadimitriou programme, completed ~2000s refinements), and the conjecture is proven for broad metric families: lines, trees, spaces of bounded size, and more. The randomized analogue saw genuine breakthroughs recently (Bubeck and co-authors' metrical task systems line), yet the clean deterministic statement remains the field's north star.