竞争分析

定义 ​

在在线算法模型公理库在线算法模型Online algorithm model输入逐步揭示，算法必须在未知未来时作出通常不可撤回的决策。的最小化问题中，若对所有序列

$$ALG(\sigma )\le cOPT(\sigma )+\beta ,$$

则算法 $c$-competitive；$\beta$ 与序列长度无关，用于初态和短序列。Strict competitive 要求 $\beta =0$。随机算法常比较期望成本，并必须指定对手。

Ski rental 阈值算法给近 2 的竞争比：短季节只租，长季节多付不到一次购买价。长期平均表现好并不推出逐序列不等式。

(\beta) 不能随序列长度增长，否则任何线性差都能被藏进加性项。Asymptotic competitive ratio 允许固定初态差，关注 (\operatorname{OPT}(\sigma)\to\infty) 时的比值上极限。

消歧 ​

近似比比较同一完整输入上的可计算解与 NP 优化最优；竞争比还受未来不可见限制。Regret 是加性差且常与固定动作比较。最大化问题比率方向需改写，OPT 为零也要处理。

资源增广比较不同资源下的 ALG 与 OPT，例如在线分页给更大缓存；这不是原竞争比的直接改进，必须把两侧资源写进符号。经验 workload 上的平均比率也不是对所有序列的竞争保证。

量词与随机对手 ​

确定性定义先固定算法，再要求对每个序列不等式成立。随机算法面对 oblivious 对手时，先固定序列 $\sigma$，再取 ${\mathbb{E}}_{r}AL{G}_r(\sigma )$；adaptive 对手可按历史动作选请求，序列本身依 $r$，不能使用同一交换顺序。

Yao 原理为随机下界选择一个输入分布，证明每个确定算法在该分布下期望比率大；它不给随机算法上界，也不能把单个最坏序列分布化后直接使用。

势函数逐轮证明 ​

Paging/LRU 一类证明可设势衡量 ALG 与 OPT 缓存差异，逐请求验证

$$cos{t}_A+\mathrm{\Delta }\mathrm{\Phi }\le ccos{t}_{OPT}.$$

求和后中间势消去，若 $0\le {\mathrm{\Phi }}_T$ 且初势有界，得到加性常数。势函数依两个算法状态，这与只分析一个结构操作序列的摊还势不同。

短序列和加性常数 ​

若初始装载需固定成本，严格比率在 $OPT=0$ 的短序列上无定义；$\beta$ 吸收该差，但必须与序列长度无关。写成 $ALG\le (c+o(1))OPT$ 的 asymptotic 版本也要说明极限按 $OPT\to \mathrm{\infty }$。

三类比较基准 ​

Approximation ratio 给算法完整实例仍受计算限制；competitive ratio 与知道未来的离线 OPT 比；regret 通常与最好固定动作做加性比较。Ski rental 的 OPT 每序列可选租或买，不是一个固定动作跨全部序列，因此也不是普通 experts regret。

参考资料

• Sleator, Tarjan, “Amortized Efficiency of List Update and Paging Rules,” 1985.
• Borodin, El-Yaniv, 1998.