离线时间最优 k-服务器问题的困难性

《Discrete Applied Mathematics》：Hardness of the offline time-optimal k-server problem

　　

摘要 在时间最优 k-服务器问题中，两个服务器配置之间的转移时长由单个服务器行驶的最大距离决定，而非所有服务器行驶距离之和。现有工作主要从在线算法的竞争性分析角度研究该模型。我们考虑离线优化问题，即整个请求序列已提前已知。我们证明，对于高度至多为三、仅使用两种边长的加权树度量，以及无权路径的顶点度量，对应的判定问题均为强 NP 完全问题。后者意味着欧氏直线上有限子集的复杂性同样成立。上述两个结果在请求两两不同且初始服务器位置互不相同的情形下依然成立。

引言 在经典 k-服务器问题中，需要由 k 个移动服务器处理度量空间中的一系列请求。在标准距离模型中，转移的代价为所有服务器行驶距离之和。该问题由 Manasse、McGeoch 和 Sleator [9] 提出，并成为在线计算理论中的核心问题之一 [4]、[6]。

在时间模型中，距离之和被替换为最大值。所有服务器可同时移动，转移时长由某个服务器行驶的最大距离决定。这一替换不仅改变了目标函数，也改变了最优服务策略。不处理当前请求的服务器可以同时移动以应对未来请求，而不会增加转移时长——前提是其移动距离小于已经所需的最长移动距离。

本文研究时间模型的离线版本，即度量、初始配置和整个请求序列均已提前已知。据我们所知，在此之前该问题的计算复杂性尚未被确定。我们证明，即使局限于两个本质上受限的度量类，判定问题也是强 NP 完全问题：一是仅使用两种边长、高度至多为三的加权树度量，二是无权路径的顶点度量。后者即欧氏直线上连续整数点的度量。两个结果均适用于请求两两不同且初始服务器位置互不相同的情形。这与经典距离模型形成鲜明对比，后者中离线最优解可在多项式时间内求得 [1]。因此，复杂性专门源于同步移动的最大值机制，而非继承自普通 k-服务器问题。

离线问题的复杂性不仅在直接求解离线问题时具有重要意义，它也关系到在线方法的构建。具体而言，工作函数算法的决策依赖于以指定最终配置服务已请求前缀的最优代价 [7]。Frei 等人将时间模型中工作函数算法的研究确定为自然的后续步骤 [4]。我们的结果揭示了直接实现所面临的计算障碍：假设可以访问时间模型的精确多项式时间离线预言机。除非 P=NP，否则一般情况下无法在多项式时间内实现这样的精确离线预言机。同时，该结果并未排除高效的在线算法、近似离线子程序，或针对特殊输入类的多项式时间算法的可能性。

对于经典距离模型，研究传统上侧重于竞争性分析 [4]、[6]。树度量是该问题的主要特殊类之一，并拥有专门的算法结果 [2]、[6]。特别是这一点，促使我们在下文考虑树度量情形。在离线设定下，经典问题要容易得多。借助最小费用网络流，可在多项式时间内求出有限度量上的最优服务策略 [1]。

时间变体由 Fiat、Rabani 和 Ravid 明确表述为最小时间服务器问题 [3]。另见 Koutsoupias 和 Taylor 的历史综述 [8]。在该模型中，服务器同时移动，算法最小化处理所有请求所需的总时间 [4]、[8]。Koutsoupias 和 Taylor 获得了该模型的首批专用界限，包括树度量上的界限 [4]、[8]。Frei 等人以"时间最优 k-服务器"之名开启了对该问题的系统研究，并分别考虑了欧氏度量和一致度量空间 [4]。这些方向为我们的复杂性定理中所使用的两个度量类提供了动机。

一个相关的变体——最小化单个服务器的累积最大行程——由 Xu、Li、He 和 Luo [10] 进行了研究。与离线最优解的竞争性比较本身并不提供计算该最优解的算法，也不决定对应离线问题的复杂性。

子章节片段 问题形式化 设 M=(X,d) 为有限度量空间，k 为正整数。记 [k]?{1,…,k}。k 个有标签服务器的配置是一个映射 C:[k]→X。该映射不必是单射，因此多个服务器可以占据同一点。一个实例由初始配置 C0 和请求序列 σ=(r1,…,rN)，rt∈X 组成。

定义 2.1 可行调度 可行调度是配置序列 C0,C1,…,CN，其中在每个对应步骤后每个请求都被覆盖：对于每个 t∈[N]，rt∈im(Ct)。转移 t 的时长为

从顶点覆盖的归约 归约自 NP 完全的顶点覆盖问题 [5]。一个实例由简单无向无权图 G=(V,E) 和整数 K 组成。问题是 G 是否存在大小至多为 K 的顶点覆盖。

设 |V|=n，|E|=m。我们首先描述主要构造，即 m≥1，0≤K≤m 情形下的构造。固定 V=(u1,…,un) 和 E=(e1,…,em) 的任意排序，设 D?m+1。对于顶点 u，令 δ(u) 表示与 u 关联的边集合。

归约的正确性 我们首先描述由给定顶点覆盖出发的服务策略。

引理 4.1 若图 G 存在顶点覆盖 A?V，则所构造实例的请求可在至多 D+|A| 的时间内完成服务。

证明 我们描述一种服务策略。对于每条边 e={u,v}，选择一个端点 a(e)∈A∩{u,v}，令 A'?{a(e):e∈E} 为该选择的像。

在第一请求时，对每条边 e 同时执行：将服务器从 Ra(e),e 移动到 Be。每个这样的服务器行驶距离 D，因此转移的时长恰为 D。

结论 本文建立了以时间最小化为目标函数的离线 k-服务器问题的计算复杂性。其判定版本在高度至多为三的加权树度量上以及无权路径的顶点度量上均为强 NP 完全问题，即使请求两两不同且初始服务器位置互不相同亦然。特别地，欧氏直线上有限子集的复杂性同样成立。

未来研究的自然方向包括近似算法的设计，以及

Oleg Lomachenko