k-server 猜想成立

# k-server猜想成立
来源：https://arxiv.org/html/2609.15979
2026年9月14日

###### 摘要
k-server猜想指出，对于所有度量空间，存在确定性在线算法可达到竞争比k。我们证明了该猜想，特别地，证明了工作函数算法满足此性质。我们的证明采用工作函数的自然代数矩阵表示，该矩阵编码了到达配置的所有可行路径。在此表示中，最优成本定义中出现的最小值与加法操作对应于形式表达式的加法和乘法，每个工作函数值对应于矩阵k列的行列式。请求到达通过基变换和行替换更新该表示。摊还分析基于一个势函数，该势函数定义于一个更大的矩阵，其坐标是原矩阵表示坐标的配对。

## 1 引言
k-server问题由Manasse、McGeoch和Sleator[53 (https://arxiv.org/html/2609.15979#bib.bib48)]提出，是竞争分析中的核心问题。它被反复称为该领域的"圣杯"[21 (https://arxiv.org/html/2609.15979#bib.bib21), 4 (https://arxiv.org/html/2609.15979#bib.bib4), 33 (https://arxiv.org/html/2609.15979#bib.bib33), 51 (https://arxiv.org/html/2609.15979#bib.bib47), 26 (https://arxiv.org/html/2609.15979#bib.bib28), 28 (https://arxiv.org/html/2609.15979#bib.bib27), 40 (https://arxiv.org/html/2609.15979#bib.bib38), 32 (https://arxiv.org/html/2609.15979#bib.bib32), 41 (https://arxiv.org/html/2609.15979#bib.bib39), 16 (https://arxiv.org/html/2609.15979#bib.bib16)]，许多最初为k-server问题开发的技术后来影响了在线算法的其他多个问题。该问题的定义很简单：k个服务器位于度量空间的点上。在每个时间步，一个请求到达度量空间的某一点。在线算法必须在不了解未来请求的情况下立即将一个服务器移动到请求位置来服务请求，目标是使服务器移动的总距离最小化。在引入该问题时，[53 (https://arxiv.org/html/2609.15979#bib.bib48)]证明了对于任何具有n>k个点的度量空间，任何确定性在线算法的竞争比至少为k，证明了在k=2或n=k+1时该下界是紧的，并猜想在一般情况下该下界也是紧的。这个问题后来被称为*k-server猜想*，并成为推动竞争分析进展的动力。

首个在一般度量空间上具有有限竞争比的算法出现在[38 (https://arxiv.org/html/2609.15979#bib.bib36)]，达到了关于k的指数级竞争比。该结果在[42 (https://arxiv.org/html/2609.15979#bib.bib40)]和[8 (https://arxiv.org/html/2609.15979#bib.bib8)]中使用（随机化）调和算法改进为更小的指数级，该算法可以使用[11 (https://arxiv.org/html/2609.15979#bib.bib11)]中的技术去随机化。Koutsoupias和Papadimitriou[47 (https://arxiv.org/html/2609.15979#bib.bib45)]取得了显著改进，他们证明了*工作函数算法（WFA）*在一般度量空间上的竞争比为(2k-1)。该结果的另一个证明见于[49 (https://arxiv.org/html/2609.15979#bib.bib60)]。WFA首次出现在[25 (https://arxiv.org/html/2609.15979#bib.bib25)]，同时也由Karloff以及McGeoch和Sleator独立提出。其定义简单且通用，远远超出了k-server问题：对于配置X（例如k-server问题中k个服务器的位置）和时间t，用w_t(X)表示服务完时间t的所有请求后结束于配置X的最小（离线）成本。函数w_t称为工作函数，其值可以在时间t在线计算。WFA在每个时间步移动到使其工作函数值加上从前一配置移动到该配置的成本（距离）之和最小的配置。对于WFA，k的猜想界已在许多特殊情况下得到证明，包括k=2 [25 (https://arxiv.org/html/2609.15979#bib.bib25)]，n=k+1（常识，参见[50 (https://arxiv.org/html/2609.15979#bib.bib43)]），n=k+2 [48 (https://arxiv.org/html/2609.15979#bib.bib46)]，线度量[9 (https://arxiv.org/html/2609.15979#bib.bib9)]，加权星形度量[9 (https://arxiv.org/html/2609.15979#bib.bib9)]（等价于加权分页问题），多射线度量[28 (https://arxiv.org/html/2609.15979#bib.bib27)]，曼哈顿平面上的k=3 [10 (https://arxiv.org/html/2609.15979#bib.bib10)]，树上的k=3 [28 (https://arxiv.org/html/2609.15979#bib.bib27)]，以及圆上的k=3 [44 (https://arxiv.org/html/2609.15979#bib.bib42)]。此外，双重覆盖算法在线上[23 (https://arxiv.org/html/2609.15979#bib.bib23)]，以及更一般地在树上[24 (https://arxiv.org/html/2609.15979#bib.bib24)]达到了猜想的k界。我们证明了WFA在一般度量空间上是k竞争的，从而证实了k-server猜想。

### 1.1 预备知识与我们的结果
k-server问题定义在度量空间(M,d)上。k个服务器起始于位置s_1, ..., s_k ∈ M，并在线揭示请求序列r_1, ..., r_T ∈ M。为方便起见，我们用M := {s_1, ..., s_k, r_1, ..., r_T}表示对应的k+T个不同位置标签集。然后d在M上诱导出一个伪度量；它可能只是伪度量而非度量的原因是，M可能包含相同点但距离为零的不同标签。配置是M的一个k元素子集，代表k个服务器的位置。对于配置X = {x_1, ..., x_k}和Y = {y_1, ..., y_k}，它们的距离定义为：
D(X,Y) = min_{σ ∈ S_k} ∑_{i=1}^k d(x_i, y_{σ(i)}).  (1)
这是将服务器从X移动到Y的最小成本。记初始配置为C_0 = {s_1, ..., s_k}。在每个时间步t，算法必须通过移动到配置C_t ∋ r_t来服务当前请求r_t，支付移动成本D(C_{t-1}, C_t)。目标是最小化总成本。

工作函数是将配置X映射到服务完前t个请求后移动到配置X的最小（离线）成本的函数w_t。众所周知（例如参见[50 (https://arxiv.org/html/2609.15979#bib.bib43)]），工作函数可以通过动态规划在线计算，通过w_0(X) = D(C_0, X)和递推关系：
w_t(X) = \begin{cases} w_{t-1}(X), & r_t \in X, \\ \min_{x \in X} \{ w_{t-1}(X - x + r_t) + d(r_t, x) \}, & r_t \notin X. \end{cases}  (2)
因此，总最优离线成本可表示为OPT_{C_0}(r_1, ..., r_T) = min_X w_T(X)。

工作函数算法（WFA）在时间步t在配置C_t ∋ r_t中服务请求，该配置使w_t(C_t) + D(C_{t-1}, C_t)最小化。为简单起见，我们在此假设一种惰性实现，其中C_t ⊆ C_{t-1} ∪ {r_t}，尽管我们的结果可扩展到任何其他打破平局的规则。我们用WFAC_0(σ)表示WFA在请求序列σ上的成本。

以下标准记账论证是Chrobak和Larmore[25 (https://arxiv.org/html/2609.15979#bib.bib25)]的扩展成本法：我们不直接界定WFA的成本D(C_{t-1}, C_t)，而是界定所谓的扩展成本max_X (w_t(X) - w_{t-1}(X))。为完整起见，我们将其证明包含在附录中。

###### 引理1.1（扩展成本记账[25 (https://arxiv.org/html/2609.15979#bib.bib25)]）。
设C_0, C_1, ..., C_T是任意WFA轨迹，并设ExtCost_t = max_X (w_t(X) - w_{t-1}(X))。则
WFAC_0(r_1, ..., r_T) + w_T(C_T) ≤ ∑_{t=1}^T ExtCost_t.  (3)

对于配置X = {x_1, ..., x_k}，定义其团权重为cl(X) = ∑_{1 ≤ i < j ≤ k} d(x_i, x_j)。注意cl(X) = (1/2) (∑_x w(X) - cl(X))。我们观察到以下有用的引理。

###### 引理1.2（[47 (https://arxiv.org/html/2609.15979#bib.bib45)]）。
对于任何配置X和请求r，有w(X) + cl(X) ≤ w(X - x + r) + cl(X - x + r) + 2d(r, x)对于某个x ∈ X成立。

这允许我们限制工作函数的增加。我们证明的主要新贡献是以下定理。

###### 定理1.3（主要定理）。
对于所有度量空间，WFA是k竞争的。具体而言，对于任何请求序列σ和任何初始配置C_0，有WFAC_0(σ) ≤ k · OPT_{C_0}(σ) - w_T(C_T)。

结合引理1.1，这证明了k-server猜想。

*随机化k-server猜想*指出，存在对于所有度量空间的O(log k)竞争的随机化算法，在[17 (https://arxiv.org/html/2609.15979#bib.bib20)]中通过一个Ω(log^2 k)的下界被反驳，该下界在某些度量空间上成立，甚至当n=k+1时。首个针对任意n点度量空间的polylog(k,n)竞争算法在[3 (https://arxiv.org/html/2609.15979#bib.bib3)]中实现，并在[20 (https://arxiv.org/html/2609.15979#bib.bib18)]中改进为O(log n log^2 k)和O(log Δ log^3 k)，其中Δ是度量空间最大与最小非零距离之比。由于n和Δ都可能是无限的，目前尚不清楚随机化在一般度量空间上是否提供优势，即使允许随机化，目前已知的最佳竞争比也由WFA实现。

## 2 从min-plus递推到行列式列
本节从基本原理发展代数状态。贯穿全文，z是一个形式符号，其指数表示成本。我们使用额外变量作为系数来区分组合选择；它们的值从不具体化为数字。每当它们用于索引行列式列时，我们为配置指定一个顺序。

### 2.1 形式表达式及其最低指数
对于每个初始服务器索引i ∈ [k]和位置标签x ∈ M，引入一个独立变量γ_{i,x}。对于每个时间t ∈ [T]和标签x ∈ M，引入一个独立变量ξ_{t,x}。设F为所有这些变量在Q上的有理函数域。考虑有限形式和f = ∑_{a ∈ A} f_a z^a, A ⊆ ℝ有限，f_a ∈ F。合并相同指数时进行加法，乘法使用z^a z^b = z^{a+b}。如果f ≠ 0，定义ν(f) = min{a: f_a ≠ 0}；ν(0) = ∞。例如，ν(3z^2 - 7z^5) = 2且ν(z^{-1} + z^4) = -1。系数域F中的每个非零元素的赋值为零。两个非零和乘积中的最低指数项是其最低指数项的乘积。其系数非零，因为F是域。因此这些有限和没有零因子。我们可以形成它们的分式域K并扩展定义为ν(f/g) = ν(f) - ν(g) (fg ≠ 0)。这是定义良好的：如果f/g = f'/g'，则fg' = f'g，取这些乘积的最低指数得到相同的差值。我们将使用的两个规则是：
ν(ab) = ν(a) + ν(b), ν(a + b) ≥ min{ν(a), ν(b)}.  (5)
第二个不等式可以是严格的。例如，z^2 + (-z^2 + z^5) = z^5。正是这个消去问题在用代数递推替换min-plus递推时需要小心。

###### 引理2.1（新系数防止消去）。
假设f_1, ..., f_m ∈ K不使用任何独立的系数变量η_1, ..., η_m。对于实数a_1, ..., a_m，如果至少一个f_i非零，则
ν(∑_{i=1}^m η_i z^{a_i} f_i) = min_i (a_i + ν(f_i)).
###### 证明。
将f_i放在一个不使用任何η_i的公共非零分母上。在此乘法之后，所有项都是有限和。在右边出现的最小指数处，左边的系数是非空和∑_{i∈I} η_i b_i，其中非零b_i独立于所有η_j。它不可能为零：清除系数分母后，它是关于不同独立变量η_i的线性非零多项式。除以公共分母即得断言。∎

### 2.2 初始匹配作为行列式
对于每个标签x ∈ M，包括初始标签本身，定义列q_x ∈ K^k为
(q_x)_i = γ_{i,x} z^{d(s_i, x)}, i ∈ [k].  (6)
因此一个统一的公式定义了所有列。如果X = (x_1, ..., x_k)具有不同的标签，令
u_0(X) = det(q_{x_1}, ..., q_{x_k}).
行列式展开为
u_0(X) = ∑_{σ ∈ S_k} sgn(σ) (∏_{i=1}^k γ_{i, x_{σ(i)}}) z^{∑_{i=1}^k d(s_i, x_{σ(i)})}.  (7)
每项的指数是从C_0到X的匹配成本。不同的排列给出不同的系数单项式，即使它们的匹配成本相等。因此最低成本项不会消去，且
ν(u_0(X)) = D(C_0, X) = w_0(X).  (8)
特别是，每k个不同列构成一个基。对于两个服务器，此构造写为：
u_0(x,y) = γ_{1,x} γ_{2,y} z^{d(s_1,x) + d(s_2,y)} - γ_{1,y} γ_{2,x} z^{d(s_1,y) + d(s_2,x)}.
两种可能的分配具有相反的符号。如果它们的成本平局，它们的系数仍然不同，因此最小成本存活。使用独立符号而非单位系数对于这个简单论证至关重要。

### 2.3 请求作为行替换
我们现在维护列q_x ∈ K^k，使得
u(X) := det(q_{x_1}, ..., q_{x_k}), ν(u(X)) = w(X)  (9)
对于每个不同标签的有序配置。交换两个标签会改变u(X)的符号，但保持其赋值不变，这对于无序配置是必需的。

假设k ≥ 2且一个请求到达r。向量q_r是非零的，因为它属于k个不同列的基。我们首先改变坐标使得q_r = e_1，同时精确保持每个行列式。

###### 引理2.2（行列式保持标准化）。
对于每个非零v ∈ K^k，k ≥ 2，存在一个可逆矩阵B满足Bv = e_1且det B = 1。
###### 证明。
高斯消元。∎

在应用引理2.2后，我们有q_r = e_1。对于任何配置X，如果r ∈ X，则将r的列与其他列交换使得r出现在第一个位置，行列式乘以-1的符号，但赋值不变。因此，不失一般性，我们假设r = x_1。然后u(X) = det(e_1, q_{x_2}, ..., q_{x_k}) = det(q_{x_2}, ..., q_{x_k})。

现在，我们想要更新列以反映请求r的服务。新的配置可能包含r，也可能不包含。我们考虑两种情况。

情况1：r ∈ X。那么w_t(X) = w_{t-1}(X)。我们可以通过设置q'_x = q_x对于x ≠ r和q'_r = e_1来保持此状态。那么u'(X) = u(X)，因此ν(u'(X)) = w_{t-1}(X) = w_t(X)。

情况2：r ∉ X。那么w_t(X) = min_{x ∈ X} { w_{t-1}(X - x + r) + d(r, x) }。我们想要一个新列集，使得ν(u'(X))等于此值。注意对于任何x ∈ X，我们有w_{t-1}(X - x + r) = ν(u(X - x + r))。此外，d(r, x)是请求r与x之间的距离。我们可以通过修改列来实现这一点。

具体而言，我们定义新列q'_x = q_x + z^{d(r,x)} e_1对于x ≠ r，且q'_r = e_1。然后对于任何配置X不包含r，计算u'(X) = det(q'_x : x ∈ X)。使用行列式的多线性性质，我们可以将其展开。

关键观察是，由于q_r = e_1，矩阵[e_1, q_{x_2}, ..., q_{x_k}]的第一行是(1, 0, ..., 0)。因此，当我们计算det(q'_x : x ∈ X)时，第一行将涉及q'_x的第一个分量。由于q'_x = q_x + z^{d(r,x)} e_1，其第一个分量是(q_x)_1 + z^{d(r,x)}。但(q_x)_1 = γ_{1,x} z^{d(s_1,x)}。

然而，为了正确处理组合选择，我们需要确保最低指数项对应于所需的最小值。这就是为什么我们需要新的独立变量ξ_{t,x}，它们尚未使用。我们实际上将q'_x设置为q_x + ξ_{t,x} z^{d(r,x)} e_1。然后，当展开行列式时，每个排列σ对应于为每个位置i选择一个项。最低指数项将对应于为每个x选择项ξ_{t,x} z^{d(r,x)} e_1或q_x中的项，具体取决于哪个给出更小的指数。

通过适当选择ξ_{t,x}为新变量，我们可以确保消去不会发生，并且ν(u'(X))正好是min_{x ∈ X} {ν(u(X - x + r)) + d(r, x)} = w_t(X)。这完成了从工作函数到代数表示的归纳步骤。

此代数表示是分析WFA的关键工具。通过研究矩阵列如何随时间演变，我们可以限制扩展成本，从而得到主要定理。详细分析涉及跟踪赋值如何变化并应用势函数，该势函数定义于由配对坐标构建的更大矩阵上。这种技术提供了k-server问题解法所需的新见解。