k-Server 问题 | Codeboy's Blog

形式陈述

请求协议与配置

给定度量空间 $(X,d)$ 、整数服务器数 $k\ge1$ 和初始配置 $C_0$ 。配置是 $X$ 上含重数的 $k$ 元集合；服务器可重合，若模型禁止重合必须另行说明。第 $t$ 轮先揭示请求点 $r_t\in X$ ，算法随后选择新配置 $C_t$ ，要求 $r_t\in C_t$ 。

从 $C_{t-1}$ 变到 $C_t$ 的成本，是旧服务器与新服务器之间最小完美匹配的距离和：

D(C_{t-1},C_t)= \min_{\pi\in S_k}\sum_{i=1}^k d(x_i,y_{\pi(i)}).

标准请求只需把一台服务器移到 $r_t$ ，但用配置距离写法能消除服务器标签；同一次响应中绕路或额外移动不会比直接匹配更便宜。

若请求点已被占据，可以令 $C_t=C_{t-1}$ ，本轮成本为零。算法只看见 $r_1,\ldots,r_t$ ，不能用未来请求决定当前移动；这正是在线协议的约束。

竞争比与量词

固定同一初始配置 $C_0$ ，令 $ALG(\sigma)$ 与 $OPT(\sigma)$ 分别是在线算法和预知完整序列的离线最小移动成本。确定算法若存在与序列无关的常数 $\beta$ ，使所有有限序列满足

ALG(\sigma)\le c\,OPT(\sigma)+\beta,

就称为 $c$ -competitive。若两侧初态不同， $\beta$ 必须吸收初始配置距离；不写初态便无法比较短序列。

随机算法面对 oblivious 对手时，先固定请求序列，再对算法内部随机性取期望：

\forall\sigma:\quad \mathbb E_r[ALG_r(\sigma)] \le c\,OPT(\sigma)+\beta.

能依据过去随机动作选择下一请求的 adaptive 对手改变了量词，不能直接沿用 oblivious 上界。竞争比的共同定义与势函数账本见竞争分析。

直觉

每次响应不仅支付把一台服务器送到请求点的距离，也留下下一轮使用的配置。在线算法看不见未来，因而要在相同即时成本的多个移动中承担状态选择风险；竞争比正是把这项信息劣势与预知完整请求序列的 OPT 比较。

直线度量上两台服务器响应三个请求并留下不同后续配置 — k-Server 的移动成本与配置选择

例子与边界

两台服务器的直线轨迹

在实线度量上，初态为 $C_0=\{0,10\}$ ，请求依次为 $4,7,2$ 。一种在线轨迹是：

请求 4 时把 0 处服务器移到 4，付 4，配置变为 $\{4,10\}$ ；
请求 7 时选择 10 处服务器，付 3，配置变为 $\{4,7\}$ ；
请求 2 时移动 4 处服务器，付 2，总成本为 9。

第二步若改为把 4 移到 7，只付 3，却留下 $\{7,10\}$ ，第三步要再付 5。局部成本相同的选择会产生不同未来状态，而在线算法在第二步看不到请求 2；例子的重心不是某组数字，而是“当前服务点的选择同时决定下一轮配置”。

Paging 作为一致度量特例

令任意不同页面的距离均为 1。在初始服务器位置互异、且只在未占据的请求点到来时移动一台服务器的需求式实现中， $k$ 台服务器表示缓存中的 $k$ 个页面。请求页已在配置中就是 hit；否则把某台服务器移到请求页，成本 1，对应淘汰一个旧页并装入新页。因此paging是 uniform metric 上的需求式 k-server 特例。初始空槽可用永不请求的互异虚拟页填补；第一次将虚拟页换成实际页也收费 $1$ ，与空槽装入一致。

这个归约只对应缺页次数模型。若页面大小不同、换入成本不同或缓存有层级，距离未必是一致度量；若迁移成本不满足三角不等式，k-server 的度量论证也不能直接使用。

推论与应用

经典界与近期预印本

对至少含 $k+1$ 个点的一般度量，确定性竞争比下界为 $k$ 。Koutsoupias–Papadimitriou（1995）的经典结果给 Work Function Algorithm（WFA）以 $2k-1$ 的上界；将一般度量上的上界降至 $k$ ，长期称为 k-server 猜想。

2026 年 9 月 14 日，Coester、Koutsoupias 与 Zbysiński 的预印本 The $k$ -server conjecture is true（arXiv:2609.15979v1）报告了一般情形的证明，Theorem 1.2 陈述：对任意度量、同一初始配置 $C_0=\{s_1,\ldots,s_k\}$ 和每条有限请求序列，

WFA_{C_0}(\sigma)\le k\,OPT_{C_0}(\sigma) +\sum_{1\le i<j\le k}d(s_i,s_j).

这是一般度量的确定性结论，最后一项只依初始配置。此处按截至 2026 年 10 月 6 日的 v1 预印本记录其定理陈述；其工作函数矩阵表示与势函数证明不在本页展开。

有限度量、树度量、一致度量上的具体实现，以及随机算法的界，仍须连同度量类别、点数和对手模型陈述。竞争比只度量总移动距离；计算下一配置所需的时间与空间是另一层算法成本。

实现与建模边界

连续空间中服务器位置可能是实数，但请求只在有限集合上时，最优策略可常规化为只在相关点移动；若允许预测、重新放置或资源增广，比较基准必须同步修改。请求批量揭示也不是同一在线模型。

配置含重数时，不能用普通集合去重；配置距离要解最小匹配，而不是按服务器数组下标逐项相减。证明中给服务器临时命名可以方便描述，但最终成本不应依赖标签排列。

参考资料

Mark Manasse, Lyle McGeoch, Daniel Sleator, Competitive Algorithms for On-Line Problems, STOC, 1988.
Elias Koutsoupias, Christos Papadimitriou, On the k-Server Conjecture, Journal of the ACM, 1995.
Allan Borodin, Ran El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, 1998.
Christian Coester, Elias Koutsoupias, Marek Zbysiński, The $k$ -server conjecture is true, 2026-09-14, v1 预印本，§1.1、Theorem 1.2。

形式陈述 ​

请求协议与配置 ​

竞争比与量词 ​

两台服务器的直线轨迹 ​

Paging 作为一致度量特例 ​

经典界与近期预印本 ​

实现与建模边界 ​