悬挂数十年的 k-server 猜想被证明，arXiv 论文给出完整证明

ctjlewis · x · 2026-09-16

Christian Coester、Elias Koutsoupias 与 Marek Zbysiński 在 arXiv 发布论文，证明在线算法领域的经典难题 k-server 猜想成立：确定性在线算法可在任意度量空间上达到竞争比 k。证明思路是利用 work function algorithm，把 work function 表示为一个矩阵的代数结构——其中可行路径编码为形式表达式的加法与乘法，每个 work function 值对应矩阵 k 列的行列式；请求到达时通过换基与行替换更新表示，摊还分析则基于一个更大矩阵定义的势函数。