Coester, Koutsoupias and Zbysiński Prove the k-Server Conjecture True After Three Decades Open

arXiv / Hacker News (104pts)·medium signalXBlueskyLinkedInCopy link

arXiv 2609.15979, submitted September 14, shows a deterministic online algorithm achieves competitive ratio k on every metric space, and specifically that the work function algorithm does. The proof represents work functions as matrices encoding feasible paths to configurations, then runs an amortized analysis with a potential function over a larger matrix, so determinants and row operations correspond directly to algorithmic operations. It pulled 104 points on HN and matters to anyone building caching, scheduling or request-routing layers where the k-server bound was the open theoretical ceiling.