度量任务系统

状态、任务与揭示时序 ​

度量任务系统由有限度量空间公理库度量空间Metric space配备非负、对称、正定并满足三角不等式的距离函数的集合。 $(X,d)$ 与初始状态 $x_0\in X$ 构成。第 $t$ 轮先完整揭示非负服务成本向量

$$c_t:X\to {\mathbb{R}}_{\ge 0}\cup \{+\mathrm{\infty }\},$$

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

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

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

$+\mathrm{\infty }$ 可表达本轮禁止使用的状态；实际实现可用大于任何可行总成本的哨兵，但要避免整数溢出。状态数记为 $m=|X|$，它会进入一般竞争比。

离线工作函数 ​

定义工作函数 $w_t(x)$：服务前 $t$ 个任务并最终停在 $x$ 的离线最小成本。固定初态后，基例为 $w_0(x)=d(x_0,x)$，递推为

$$w_t(x)=c_t(x)+\underset{y\in X}{min}(w_{t-1}(y)+d(y,x)).$$

这个递推既允许第 $t$ 轮从任意旧状态迁移，又把服务费只计一次。由三角不等式，工作函数满足 $w_t(x)\le w_t(y)+d(x,y)$，即对状态位置是 1-Lipschitz；许多势函数证明依赖这一不变量。

离线最优值是 $\underset{x}{min}{w}_T(x)$。在线 Work Function Algorithm 的一种标准写法，在第 $t$ 轮选择最小化

$$w_t(x)+d(x_{t-1},x)$$

的状态，并固定一致的 tie-breaking。$w_t$ 用当前及过去任务，可以在线计算；它不是偷看未来的 $w_T$。

两种电源状态的轨迹 ​

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

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

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

与 k-Server 的关系 ​

MTS 的请求是整个状态成本向量；k-Server公理库k-Server 问题k-server problem · k 服务器问题在度量空间中在线移动 k 台服务器响应请求，以总移动距离同预知未来的最优策略比较。 的请求是一个必须被某服务器占据的点。可把 k-server 的每个服务器配置视为 MTS 状态，状态间距离取配置匹配距离，并令“包含请求点”的配置服务费为 0、其余为 $+\mathrm{\infty }$。

这个编码的状态数可能是 $(\genfrac{}{}{0ex}{}{|X|+k-1}{k})$ 量级，所以它建立表达能力关系，却不自动给出高效实现或有用竞争比。反方向把任意 MTS 看成点请求也不成立，因为一般服务向量允许多个状态付不同有限费用。

竞争保证 ​

确定性算法与离线 OPT 在同一初态、同一任务序列上比较，并允许与序列长度无关的加性常数。经典结果表明，含 $m$ 个状态的一般 MTS 存在 $(2m-1)$-competitive 的 Work Function Algorithm，且这个确定性因子在一般情形下是紧的。

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

计算成本与模型边界 ​

直接按递推更新所有 $w_t(x)$ 需要检查所有状态对，每轮 $O(m^2)$ 时间和 $O(m)$ 工作函数存储；竞争最优不等于计算高效。特殊度量可加速距离变换，仍需证明选择与原递推等价。

服务成本必须非负，或至少保证总问题有下界；负成本可让算法通过停留无限获利，最小化竞争比失去通常意义。任务若可拆分到多个状态、迁移可并行或状态带容量，需新模型描述。

参考资料

• Allan Borodin, Nathan Linial, Michael Saks, An Optimal On-Line Algorithm for Metrical Task Systems, Journal of the ACM, 1992.
• 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.