The $k$-server conjecture is true
Christian Coester, Elias Koutsoupias, Marek Zbysiński
cs.DS
2026-09-15
牛津三人证明 work function 算法在任意度量空间上达到 k 竞争，加性常数为初始配置团权重，确认 1988 年提出的 k-server 猜想。
k-server 问题的设定干净得像一道应用题。度量空间里放 k 台服务器，请求一个点一个点到来，每次必须立刻把某台服务器挪到请求点，总路程越短越好。在线算法看不到未来，只能跟事先知道全部请求的离线最优解比，这个最坏比值叫竞争比。
1988 年 Manasse、McGeoch、Sleator 证明，任意确定性在线算法在点数多于 k 的度量上，竞争比至少是 k。他们同时证明 k=2、以及空间刚好 k+1 个点时，这个下界是紧的，并猜想一般情况也紧。这就是 k-server 猜想。之后它反复被称作竞争分析的「holy grail」，paging、metrical task systems 上的一批技术都从这里长出来。
一般度量上，第一个有限竞争比是指数于 k 的。1995 年 Koutsoupias 和 Papadimitriou 把 work function 算法（WFA）做到 (2k−1) 竞争，这是此后 31 年一般度量上最好的确定性上界。k 本身只在一批特殊空间里被证到：直线和树（Double Coverage）、加权星（加权 paging）、点数 k+2，以及 k=3 的曼哈顿平面、树和圆。一般度量一直差着将近一倍。
WFA 的规则只有一句。对每个服务器配置 X，work function wt(X) 是「服务完前 t 个请求、最后停在 X」的离线最小代价，在线用动态规划就能维护。每次请求到来，算法走到使 wt(C) 加上搬迁距离之和最小的配置。
直接分析算法的真实移动距离很别扭。Chrobak 和 Larmore 的 extended-cost 会计把每一步换成：所有配置上 work function 的最大增量。只要找得到势函数 Ψ，满足初值等于负的初始团权重、每步增量盖住 extended cost、并且 Ψ 不超过 (k+1) 倍当前 work function 减去当前配置的团权重，再减掉终点 work function，竞争比就会掉到 k。
这篇的势不活在普通实数上。每个点 x 配一个 k 维列向量 qx，分量是带代价指数的形式表达式。任意 k 个点组成的配置，其 work function 等于这 k 列行列式的赋值，也就是最低次项的指数。min-plus 里的「取最小」和「相加」在这里变成普通加法和乘法。等代价的匹配项靠独立不定元当系数，保证不会在行列式里互相消掉。
请求到来时先换基，让被请求点的列变成第一个标准基向量，并且所有 k 列行列式保持原值；再把每一列的第一行换成与到请求点距离成比例的新值。行列式沿第一行展开，恰好复现 work function 的递推。
势函数建在对称平方上。每对列向量做成二次乘积，得到 k(k+1)/2 维空间里的一组列，再乘 z 的负距离权重。势等于这组列最大子式赋值的最小值。一个 19 世纪的行列式恒等式在这里是关键：对称平方变换的行列式等于原行列式的 (k+1) 次方。这解释了势上界里那个 (k+1)。请求更新之后，势的涨幅至少盖住 extended cost。
证明是怎么找到的，作者写得很清楚。他们先手做了一个对一般度量 k=3 成立的势，用一大族线性规划不可行来验证，这一步没有用 AI。随后和 ChatGPT 5.5 Pro、Gemini 3.1 Pro 讨论，把势改得更对称，并另写了一份 k=3 证明。再往后 ChatGPT 6 Astra 给出任意 k 的代数证明；作者提供 work function 的列表示，模型据此改写并起草了部分章节，作者再修订。
主定理对任意度量、任意有限请求序列成立：
WFA 总代价 ≤ k · OPT + cl(C0)
cl(C0) 是初始 k 台服务器位置的两两距离之和，跟请求无关。竞争比因此是 k，加性常数只取决于开局。
| 结果 | 竞争比 | 范围 |
| 任意确定性算法下界 (1988) | ≥ k | n > k 的任意度量 |
| Fiat–Rabani–Ravid (1990) | 指数于 k | 一般度量 |
| WFA，Koutsoupias–Papadimitriou (1995) | 2k−1 | 一般度量 |
| WFA，本篇 | k | 一般度量 |
随机化没有被这篇一起关掉。均匀度量和加权星上已有 O(log k) 随机算法，匹配 Ω(log k) 下界。但「所有度量都有 O(log k) 随机算法」已被 Bubeck、Coester、Rabani 证伪，某些度量上存在 Ω(log² k) 下界。当点数或直径比可以无限时，随机化是否优于确定性仍不知道；目前即便允许随机，一般度量上最好的已知竞争比仍是 WFA 的这个 k。
k-server 是在线算法的核心模型，paging 是它在均匀度量上的特例，WFA 还出现在 metrical task systems、layered graph traversal、list update、凸体追逐里。把一般度量的确定性上界从 2k−1 收到下界 k，等于把这个开了 38 年的主问题结案。
对写系统的人，WFA 本来就不是能塞进缓存策略的东西：配置空间是已见点的 k 子集，维护 work function 本身就贵。这篇的贡献是证明，不是新的可部署规则。它说明这个对很多在线问题都适用的泛用算法，在 k-server 这个最干净的实例上已经是确定性最优。
代数包装顺手把 k-server 的 work function 和 valuated matroid、热带几何、经济学里的 gross substitutes 对上了。后面若有人要把同样的势搬到加权 k-server 或 k-taxi，入口大概在这里。
证明走赋值、行列式和对称平方，不是可以在黑板上三页写完的组合论证。社区会要求独立核验，尤其致谢已经写明：任意 k 的代数证明由 ChatGPT 6 Astra 导出，部分章节由模型起草。k=3 的势和 LP 验证是作者自己做的，这一层更硬；从 3 到任意 k 的那一跳，目前公开材料就是这篇 18 页论文本身。
WFA 的计算代价这篇完全没碰。竞争比 k 是信息论意义下的最优，并不给出一个多项式时间的确定性最优在线算法。
加权 k-server、generalized k-server、k-taxi 仍然开着。随机化在无限点度量上有没有优势，也还没有答案。加性常数 cl(C0) 在初始服务器彼此很远时可以很大，虽然不影响渐近竞争比。