3 Online Algorithms
在线算法 Online Algorithms¶
在线算法（online algorithm）处理输入时，输入序列会随时间逐步到达。算法必须在看到未来输入之前作出决定，而且已经作出的决定不能撤销。
这类问题的困难通常来自信息不完整，而不是计算能力不足。分析在线算法时，通常把它与知道完整输入的离线最优算法（offline optimum）比较。
Competitive Ratio 竞争比¶
设实例为 \(I\)，在线算法为 \(ALG\)，离线最优算法为 \(OPT\)。
对于最小化问题，竞争比（competitive ratio）定义为
对于最大化问题，竞争比定义为
最小化问题的竞争比至少为 \(1\)，最大化问题的竞争比至多为 \(1\)。竞争比越接近理想值，算法的最坏情况保证越好。
竞争比与近似比（approximation ratio）形式相似，但两者的来源不同：近似算法与同一输入上的最优解比较，在线算法则与拥有更多输入信息的离线算法比较。
Ski Rental Problem 滑雪租赁问题¶
问题描述¶
滑雪者计划滑雪，但不知道旅行会持续多少天。每天可以：
- 租用滑雪板，费用为 \(1\)；
- 购买滑雪板，费用为 \(M\)，之后可以重复使用。
设实际滑雪天数为 \(T\)。离线算法知道 \(T\)，因此最优成本为
在线算法每天观察旅行是否继续，然后决定租用或购买。它不能预知 \(T\)，也不能撤销过去的选择。
两个极端策略都不理想：
- 第一天就购买：当 \(T=1\) 时，\(ALG=M\) 而 \(OPT=1\)；
- 永远租用：当 \(T\gg M\) 时，\(ALG=T\) 而 \(OPT=M\)。
因此，问题的困难来自缺少未来信息。
确定性策略¶
考虑策略 III：先租用 \(M\) 天，如果旅行仍未结束，则在第 \(M+1\) 天购买。
- 若 \(T\le M\)，算法一直租用，故
$\(ALG(T)=T=OPT(T).\)$
- 若 \(T>M\)，算法先支付 \(M\) 天租金，再支付购买费用 \(M\)，故
$\(ALG(T)=2M=2OPT(T).\)$
因此该策略是 \(2\)-competitive。
确定性下界¶
更一般地，设算法在租用 \(X\) 天后购买。若算法永远不购买，则当 \(T\) 足够大时竞争比无界；因此只考虑有限的 \(X\)。
对该策略，令旅行在第 \(X+1\) 天结束：
- 当 \(X\le M-1\) 时，
$\(OPT=X+1,\qquad ALG=X+M,\)$
因而
$$ \frac{ALG}{OPT}=\frac{X+M}{X+1} =1+\frac{M-1}{X+1}\ge 2-\frac1M. $$
- 当 \(X\ge M\) 时，
$\(OPT=M,\qquad ALG=X+M,\)$
因而
$\(\frac{ALG}{OPT}=\frac{X+M}{M}\ge 2.\)$
这说明任意确定性策略的竞争比在 \(M\) 较大时都不能显著低于 \(2\)。在通常的 ski-rental 模型中，\(2\) 是确定性算法的标准最优保证；策略“租 \(M\) 天后购买”正好达到这个上界。
对手（adversary）可以根据算法已经作出的决定选择输入长度，从而让算法在信息不足时作出代价较高的决定。
Online Bipartite Matching 在线二分图匹配¶
问题描述¶
给定无权无向二分图
一侧顶点 \(U_2\) 预先已知，另一侧顶点 \(U_1\) 逐个到达。每个 \(u\in U_1\) 到达时，算法才看到它的所有邻边。算法可以把 \(u\) 至多匹配到一个尚未使用的 \(v\in U_2\)，然后继续处理下一个到达的顶点。
匹配（matching）是没有公共端点的边集合。算法一旦加入一条边，就不能删除它，也不能回到之前到达的顶点重新匹配。目标是最大化最终匹配的边数。
该模型可以描述在线广告分配：用户加载网页对应一个到达的顶点，边表示该用户可能看到的广告主，广告主一旦被占用就不能再次使用。
Greedy 算法¶
当 \(u\in U_1\) 到达时，如果存在可用邻点，就任意选择一个可用的 \(v\in U_2\)，加入边 \((u,v)\)；如果没有可用邻点，则跳过 \(u\)。
\(1/2\)-competitive 证明¶
设算法得到的匹配为 \(ALG\)，离线最优匹配为 \(OPT\)。对每条算法加入的边 \(e=(u,v)\)，令 \(f(e)\) 为 \(OPT\) 中所有与 \(e\) 共享端点的边。
由于 \(OPT\) 本身是匹配，至多有一条边与 \(u\) 相连，至多有一条边与 \(v\) 相连，因此
另一方面，\(OPT\) 中每条边最终都被某条算法边阻塞：如果它的在线端点到达时没有被算法匹配，则算法本来可以选择它；如果该端点已经被算法匹配，则两条边共享端点。于是
因此
Greedy 算法是 \(1/2\)-competitive。
确定性下界¶
考虑两个离线顶点 \(v_1,v_2\)。第一个在线顶点 \(u_1\) 同时连接到二者。算法此时若不匹配，或者选择其中一个端点，对手都可以选择相应的后续输入，使算法最终只能得到一条边，而离线最优匹配可以得到两条边。
因此不存在竞争比严格大于 \(1/2\) 的确定性在线算法。结合 Greedy 的上界，确定性在线二分图匹配的最优竞争比为 \(1/2\)。
Online Scheduling 在线调度¶
问题描述¶
有 \(n\) 个作业（job）和 \(m\) 台相同机器（identical machines）。作业 \(j\) 的处理时间为 \(p_j>0\)。作业逐个到达，作业到达时必须立即分配到某台机器，未来作业的数量和大小未知。
更一般地，机器 \(i\) 可以有速度 \(s_i\)，作业 \(j\) 在机器 \(i\) 上的处理时间为 \(p_j/s_i\)；下面的竞争比证明针对课程重点讨论的相同机器情形，即所有 \(s_i=1\)。
设机器 \(i\) 的负载（load）为分配给它的作业处理时间之和，调度的最大完工时间（makespan）为
目标是最小化 makespan。
Least-Loaded Algorithm¶
Least-Loaded Algorithm 每次把新作业分配给当前负载最小的机器。
\((2-1/m)\)-competitive 证明¶
设算法产生的调度为 \(\pi\)，最优离线调度为 \(\pi^*\)，并令
显然，最优 makespan 至少满足
令机器 \(i\) 是算法最终负载最大的机器，令 \(j\) 是最后分配到机器 \(i\) 的作业。作业 \(j\) 到达时，机器 \(i\) 的旧负载不大于当时所有机器平均负载，因此
于是
因此 Least-Loaded Algorithm 是 \((2-1/m)\)-competitive。
\(m=2\) 时的下界¶
当 \(m=2\) 时，上界为 \(3/2\)。对手可以先给出两个大小为 \(1\) 的作业：
- 如果算法把它们放在同一台机器上，算法的 makespan 为 \(2\)，而最优值为 \(1\)；
- 否则两台机器各有一个大小为 \(1\) 的作业。此时再给出一个大小为 \(2\) 的作业，算法必须把它放在某台已有负载 \(1\) 的机器上，makespan 为 \(3\)，而最优调度可以把两个大小为 \(1\) 的作业放在一台机器上，把大小为 \(2\) 的作业放在另一台机器上，最优值为 \(2\)。
因此任意确定性算法的竞争比至少为 \(3/2\)。所以在两台相同机器上，Least-Loaded Algorithm 的保证是紧的。
Online Decision-Making Meets Stochasticity¶
当输入顺序由随机机制产生，或者算法已知输入分布时，可以利用概率分析弥补信息不足。秘书问题和先知不等式是两个经典例子。
Secretary Problem 秘书问题¶
问题描述¶
有 \(n\) 个候选人逐个到达，候选人的相对排名可以比较，但算法不知道后续候选人的排名。每个候选人到达时，算法必须不可撤销地决定录用或拒绝，目标是最大化录用全局最佳候选人的概率。
如果对手可以控制候选人的到达顺序，任何在线算法都可能在录用一个候选人后遇到更好的候选人；如果算法甚至不知道 \(n\)，对手也可以利用未知的终止时间。因此在强对手模型下不存在有界的竞争比。
经典秘书问题采用较弱的随机顺序模型：
- \(n\) 已知；
- \(n\) 个候选人的到达顺序是均匀随机排列；
- 算法最大化录用最佳候选人的概率。
三种策略¶
策略 I：直接录用第一个候选人。
最佳候选人位于第一位的概率为
策略 II：观察前一半，选择后一半中第一个超过前一半最高水平的人。
成功事件可以取为：第二佳候选人在前半段，而最佳候选人在后半段。因此
策略 III：观察前 \(n/e\) 个候选人，选择之后第一个超过观察阶段最高水平的人。
该策略的成功概率为
它是经典秘书问题的最优策略。
最优阈值的推导¶
考虑拒绝前 \(\tau\) 个候选人的阈值策略。只有当全局最佳候选人出现在位置 \(t>\tau\)，且前 \(t-1\) 个候选人中的最佳者出现在前 \(\tau\) 个位置时，算法才会在位置 \(t\) 成功录用全局最佳者。
因此成功概率为
其中 \(H_k=\sum_{i=1}^{k}1/i\) 是调和数。令 \(\tau\approx n/e\) 可以使该概率最大；当 \(n\) 足够大时，最大成功概率趋近于 \(1/e\)。
另一种理解方式是：算法不应选择一个不是“当前为止最佳”的候选人。随着位置增加，当前候选人为全局最佳的条件概率上升，而从当前位置开始仍能成功的概率下降，因此最优策略具有一个阈值结构。
Prophet Inequality 先知不等式¶
问题描述¶
有 \(n\) 个相互独立的随机变量 \(X_1,\ldots,X_n\)。算法预先知道每个随机变量的分布，但只能按 \(1,\ldots,n\) 的顺序逐个观察其实现值。看到 \(X_i\) 后，算法必须立即选择它并停止，或者拒绝它并继续；拒绝后不能返回。
算法希望最大化期望收益。先知知道所有随机变量的实现值，因此基准为
算法的收益不可能超过 \(\mathbb E[X_{\max}]\)。先知不等式研究的是：只知道分布的在线停止规则，能否保证接近这个基准。
\(1/2\) 下界¶
考虑两个随机变量：
以及
此时
如果接受 \(X_1\)，收益为 \(1\)；如果跳过 \(X_1\)，则只能接受 \(X_2\)，期望收益也是 \(1\)。因此任何在线算法的期望收益都不超过 \(1\)，从而
所以一般情况下不可能得到严格大于 \(1/2\) 的保证。
基于中位数的 \(1/2\)-competitive 策略¶
令 \(\tau\) 为 \(X_{\max}\) 的中位数，满足
策略：选择第一个满足 \(X_i\ge\tau\) 的变量。假设 \(\tau\) 处没有点质量，以避免等号处理带来的技术细节。
由于
其中 \((x)^+=\max(x,0)\)，有
算法在 \(X_{\max}\ge\tau\) 时至少获得阈值贡献 \(\tau\) 的一半期望，即贡献 \(\tau/2\)。对于超出阈值的部分，由于各变量独立，算法在看到 \(X_i\) 之前尚未停止的概率至少为 \(\Pr[X_{\max}<\tau]=1/2\)。因此
所以该阈值策略是 \(1/2\)-competitive。结合前面的困难实例，\(1/2\) 是一般独立随机变量模型下的最优常数保证。
小结¶
在线算法的核心是：输入逐步揭示，决策需要立即作出，未来信息不可用。
- Ski Rental：确定性算法的经典竞争比为 \(2\)，下界来自对手对输入长度的选择；
- Online Bipartite Matching：简单 Greedy 通过阻塞关系得到 \(1/2\)-competitive，且该保证对确定性算法是紧的；
- Online Scheduling：Least-Loaded Algorithm 在 \(m\) 台相同机器上达到 \((2-1/m)\)-competitive；
- Secretary Problem：在已知 \(n\) 且到达顺序随机时，跳过约 \(n/e\) 个候选人并选择之后第一个记录最佳者，成功概率为 \(1/e\)；
- Prophet Inequality：只知道分布的停止规则可以通过中位数阈值达到 \(1/2\)-competitive。
这些例子说明，竞争比刻画了信息限制造成的损失，而不只是算法运行时间或计算能力造成的损失。