在线算法

问题概述

在线算法：信息一个一个给出，决策不可以逆转。

对于online实例 $I = \{\sigma_1, \dots, \sigma_n\}$ ，有算法输出 $O = \{y_1, \dots, y_n\}$ 。

竞争比：设 $A$ 是一个online算法， $OPT$ 是最优的offline算法（提前知道了所有信息）。则对于最小化问题，如果存在一个常数 $\beta$ ，对任意 $I$ ，满足 $A(I) \leq c * OPT(I) + \beta$ ，则称 $c$ 的下确界为竞争比。

对于online问题的研究可以考虑以下方面：

Semi Online：可以知道一部分信息，过去做的决策可以进行有限度的更改
Online with Advice：可以知道一部分信息
Online with Imperfect Information：有建议可以参考，但不保证是对的
- 在信息相对准确时，接近离线算法，信息相对不准时，接近在线算法

一维搜索（Search on a line）：数轴上有一个点，从零点开始寻找（可能在左也可能在右）

在线竞拍（Online Bidding）：物品有一个不公开的整数的实际价值 $u \ge 1$ ，bidder可以猜测它的价值，猜价高于实际价值结束，花费的代价是所有报价之和

滑雪租鞋（Ski Rental）：不知道以后会不会去，买（花费d）还是租（花费1）

页表管理： 页表替换策略

k-server问题： 在一张图上有k个服务员，当一个点出现请求就要派一个服务员去服务，求一个方案，使得所有服务员走的总距离最小。

Online Scheduling and Load Balancing

任务分配： 有若干任务依次到来，每个任务有一个DDL，选取部分任务做使得做的最多

装箱问题： 我们前面介绍过的FF、NF等面对的装箱都是online装箱。

k-server问题： 在一张图上有k个服务员，当一个点出现请求就要派一个服务员去服务，求一个方案，使得所有服务员走的总距离最小。

定理： 在 $k$ 个server的情况下，如果至少有 $k+1$ 个点，那么竞争比的下界至少为 $k$ 。

证明： 构造bad example，假设有 $k$ 个server， $k+1$ 个点的完全图，所有边权为1。对于在线算法，每次都在没有server的那个点发出请求，则每次都要花费1去移动。而离线算法可以k个请求一组，每k个请求最多只需要移动一次。所以竞争比下界为 $k$ 。

边权任意正数 ：考虑k+1个点的图，构造k个每一步的configuration都互不相同，且也与在线算法不同的离线算法，每一步的费用之和跟在线做法花费相同，那么平均意义下花费为n/k，因此最优解肯定不会更大。

DC算法（针对on the line的题目）：如果请求点在服务员的凸包外，那么派最近的过去，如果请求点在两个服务员之间，那么两个服务员都要向请求点移动，直到有一个服务员到达。

定理：DC算法的竞争比为 $k$ 。

证明：由上面的内容我们已经知道 $k$ 是在线算法的竞争比下界，因此只需要证明上界也是 $k$ 。均摊分析证明。

Interleaving Moves： OPT和DC两个决策依次进行，比较两个决策之间的差距。如果定义势能函数 $\Phi \ge 0$ ，初始值 $\Phi_0$ 。如果OPT移动 $d$ ，则 $\Phi$ 最多增加 $kd$ ；如果DC移动 $d$ ，则 $\Phi$ 减少至少 $d$ 。这样 $\Phi_n-\Phi_0 \le k*OPT(\sigma) - DC(\sigma)$ 。
势能函数： 定义 $M_{min}$ $M_{min}$ 表示OPT决策和DC决策的 $k$ $k$ 个服务员之间的最小权完美匹配代价。定义 $s_i$ $s_{i}$ 为DC算法的服务员 $i$ $i$ 。 $\sum = \sum_{i < j}d(s_{i}, s_{j})$ $\sum = \sum_{i < j} d (s_{i}, s_{j})$ 表示DC决策中的所有服务员之间的距离之和，定义势能函数 $\Phi=k*M_{min}+\sum >0$ $Φ = k * M_{min} + \sum > 0$ 。则势能函数满足以下两条性质：
- 如果OPT决策移动了距离 $d$ ，那么 $\Phi$ 至多增加 $kd$ ： $M_{min}$ 至多增加 $d$ ， $\sum$ 不变
- 如果DC决策移动了距离 $d$ $d$ ，那么 $\Phi$ $Φ$ 至少减小了 $d$ $d$ ：
  - 如果服务点在凸包之外，那么只会移动一个点， $M_{min}$ 减小 $d$ ， $\sum$ 增加 $(k-1)d$ ， $\Phi=kM_{min}+\sum$ 减小了 $d$ 。
  - 如果服务点在凸包内，有两个点同时向它移动， $\sum$ 减小 $2d$ ，两个点到左右的距离之和变化抵消， $M_{min}$ 不会增加，考虑匹配点间连边不会增加相交，那么 $M_{min}$ 可能是一个增加 $d$ 一个减小 $d$ ，或者是两个都减小 $d$ ，代入 $\Phi=kM_{min}+\sum$ 至少减小了 $2d$