度量任务系统 | Codeboy's Blog

形式陈述

状态、任务与揭示时序

度量任务系统是竞争分析的标准在线模型，由有限度量空间 $(X,d)$ 与初始状态 $x_0\in X$ 构成。第 $t$ 轮先完整揭示非负服务成本向量

c_t:X\to\mathbb R_{\ge0}\cup\{+\infty\},

算法看见 $c_t$ 后选择状态 $x_t$ ，支付

d(x_{t-1},x_t)+c_t(x_t).

移动发生在选择新状态时，服务在新状态完成。若协议改成先服务旧状态、再看任务或只揭示被选状态的成本，信息结构已经改变，不能沿用同一竞争界。

$+\infty$ 表达本轮禁止使用的状态，计算时可显式跳过这些候选。只有已经证明所需有限上界时，才可用数值哨兵代替无穷；在线未知的未来费用不能由一个任意大常数保证覆盖。每个任务至少在一个状态具有有限服务费，否则该轮无可行服务。状态数记为 $m=|X|\ge1$ ，它会进入一般竞争比。

离线工作函数

定义工作函数 $w_t(x)$ ：从 $x_0$ 出发服务前 $t$ 个任务，允许最后一次服务后再迁到 $x$ 的最小成本。这个末端位置不必是第 $t$ 个任务的服务位置。基例与递推为

w_0(x)=d(x_0,x),\qquad p_t(y)=w_{t-1}(y)+c_t(y),\qquad w_t(x)=\min_{y\in X}\{p_t(y)+d(y,x)\}.

$p_t(y)$ 是在 $y$ 服务完本轮后立即停止的最小成本； $w_t$ 再做一次度量闭包。这是按时间与末端状态组织的动态规划。末端迁移可并入下一轮迁移而不增加成本；最后不指定终点时也无需这段额外移动，所以原服务协议的离线最优仍是 $\min_x w_T(x)$ 。

三角不等式给出 $w_t(x)\le w_t(y)+d(x,y)$ ，交换 $x,y$ 即知 $w_t$ 为 1-Lipschitz。非负服务费又给出 $w_t\ge w_{t-1}$ 。 $p_t$ 一般没有 Lipschitz 性：两状态距离为 $1$ 、初态为第一状态、首任务费用为 $(100,0)$ 时， $p_1=(100,1)$ ，但 $w_1=(2,1)$ 。服务位置与服务后的末端位置不能混用。

在线 Work Function Algorithm（WFA）在当前状态 $s_{t-1}$ 看见本轮任务后，选择

s_t\in\operatorname*{argmin}_{y\in X} \{p_t(y)+d(s_{t-1},y)\},

以预先固定规则处理并列，然后移到 $s_t$ 并在该处服务。这个写法还自动满足

w_t(s_t)=p_t(s_t),\qquad w_t(s_{t-1})=w_t(s_t)+d(s_{t-1},s_t).

由递推与对称距离，选择式先给出 $w_t(s_{t-1})=p_t(s_t)+d(s_{t-1},s_t)$ 。Lipschitz 性和 $w_t(s_t)\le p_t(s_t)$ 再给出

w_t(s_{t-1})\le w_t(s_t)+d(s_{t-1},s_t)\le p_t(s_t)+d(s_{t-1},s_t)=w_t(s_{t-1}),

所以两处不等式都必须取等。因此，它等价于在最小化 $w_t(y)+d(s_{t-1},y)$ 的状态中，选择同时满足 $w_t(y)=p_t(y)$ 的服务位置。[2, §2] 只按前一个式子任意打破平局可能选到禁止服务的状态：在上述例子把 $100$ 改为 $+\infty$ ，两状态的该评分同为 $2$ ，却只有第二状态可服务。

直觉

MTS 在“迁到更适合当前任务的状态”与“避免为短暂变化反复迁移”之间权衡。工作函数把服务到当前轮并停在每个状态的离线最小历史成本全部保留下来，度量的三角不等式又限制这些值在相邻状态间变化过快，从而给在线决策提供势能结构。

睡眠与活动状态之间的在线轨迹同时支付迁移费和服务费 — 度量任务系统的移动与服务成本

例子与边界

两种电源状态的轨迹

设状态为 sleep 与 active，相互迁移成本 4，初态 sleep。三轮任务向量依次为 $(1,6)$ 、 $(7,1)$ 、 $(7,1)$ ，坐标顺序为 (sleep,active)。

第一轮留在 sleep 付 1；第二轮若切到 active，付移动 4 和服务 1，累计 6；第三轮留在 active 再付 1。若第二轮仍睡眠，会立即付 7，并可能在第三轮才迁移。状态迁移成本让“本轮服务最便宜的状态”未必是总成本最小的在线动作。

这个例子也说明服务成本和移动成本不可合并成一个静态优先级：同一个任务向量在不同当前状态下有不同决策成本，连续相似任务又会摊薄一次迁移。

图示是一条可行轨迹，并非 WFA 在这三轮上的执行。按上述递推，从 $w_0=(0,4)$ 出发，有

轮次	服务后立即停止的 $p_t$	允许末端迁移的 $w_t$	WFA 服务位置	本轮实际成本
1	$(1,10)$	$(1,5)$	sleep	$1$
2	$(8,6)$	$(8,6)$	sleep	$7$
3	$(15,7)$	$(11,7)$	active	$4+1=5$

WFA 总成本为 $13$ ，离线最优为 $\min w_3=7$ ，由图示路径达到。竞争保证控制所有任务序列上的最坏比较，不要求这条短序列上也选择离线最优路径。

与 k-Server 的关系

MTS 的请求是整个状态成本向量；k-Server 的请求是一个必须被某服务器占据的点。对有限的底层度量，可把 k-server 的每个服务器配置视为 MTS 状态，状态间距离取配置匹配距离，并令“包含请求点”的配置服务费为 0、其余为 $+\infty$ 。

若底层点数为 $n$ ，允许重合的配置数恰为 $\binom{n+k-1}{k}$ ，所以它建立表达能力关系，却不自动给出高效实现或有用竞争比。反方向把任意 MTS 看成点请求也不成立，因为一般服务向量允许多个状态付不同有限费用。

推论与应用

竞争保证

确定性算法与离线 OPT 在同一初态、同一任务序列上比较，并允许与序列长度无关的加性常数。经典结果表明，含 $m$ 个状态的一般 MTS 的最优确定性因子为 $2m-1$ 。[1] 上述 WFA 的上界可以直接由工作函数记账证明。

令 $\Delta_t(x)=w_t(x)-w_{t-1}(x)\ge0$ 、 $e_t=\max_x\Delta_t(x)$ ，本轮实际费用为 $a_t=d(s_{t-1},s_t)+c_t(s_t)$ 。由两个选择恒等式，

a_t=w_t(s_{t-1})-w_{t-1}(s_t),

从而

a_t+w_t(s_t)-w_{t-1}(s_{t-1}) =\Delta_t(s_{t-1})+\Delta_t(s_t) \le2e_t\le2\sum_x\Delta_t(x).

对各轮相加，并用 $w_0(s_0)=0$ ，得到

ALG\le2\sum_x\bigl(w_T(x)-w_0(x)\bigr)-w_T(s_T).

取 $z$ 使 $w_T(z)=OPT$ ，由 Lipschitz 性有 $w_T(x)\le OPT+d(x,z)$ ，而 $w_T(s_T)\ge OPT$ 。若有限度量的直径为 $D$ ，舍去非正初始项即得安全界

ALG\le(2m-1)OPT+2mD.

加性项仅依固定度量，不随任务序列增长。这个证明保留了 $+\infty$ 禁用项：每轮至少一个有限服务状态，使闭包后的所有 $w_t$ 仍有限。

随机竞争比必须注明对手。面对 oblivious 对手，可先固定任务序列再对随机迁移取期望；adaptive 对手若依据过去状态选择下一成本向量，证明需要更强量词。更专门的度量族与随机算法可以得到更小界，但不能省略状态数或度量假设。

FRT随机树嵌入提供把有限度量转成层级树的工具。对抽树前固定的一条状态路径，其移动费用是固定非负点对权重的和，期望树费用至多放大O(log m)，且每份树都不缩短原距离。将它用于在线算法还须证明树上策略、可行解转换及对手条件；看见树后再选择最坏路径，不属于这个固定路径保证。

计算成本与模型边界

直接按递推更新所有 $w_t(x)$ 需要检查所有状态对，每轮 $O(m^2)$ 次算术与比较、 $O(m)$ 额外工作存储；给定的稠密距离表另占 $O(m^2)$ 空间，数值位成本另计。竞争最优不等于计算高效。特殊度量可加速距离变换，仍需证明选择与原递推等价。

本模型采用非负服务费。若允许负费用，有限序列的总成本仍可能有限，但 $OPT$ 可以为负，通常的乘法竞争保证便不再表达相同的近似意义。任务若可拆分到多个状态、迁移可并行或状态带容量，需新模型描述。

参考资料

[1] Allan Borodin, Nathan Linial, Michael Saks, An Optimal On-Line Algorithm for Metrical Task System, Journal of the ACM 39(4), 1992, pp. 745–763.
[2] Guido Schäfer and Naveen Sivadasan, Topology Matters: Smoothed Competitiveness of Metrical Task Systems, STACS 2004 作者稿，§2、式 (1)–(2)：服务后迁移的工作函数与 WFA 的额外选点条件。
Allan Borodin, Ran El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, 1998.
Amos Fiat, Gerhard Woeginger (eds.), Online Algorithms: The State of the Art, Springer, 1998.

形式陈述 ​

状态、任务与揭示时序 ​

离线工作函数 ​

两种电源状态的轨迹 ​

与 k-Server 的关系 ​

竞争保证 ​

计算成本与模型边界 ​

反向链接