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

对于online实例 I={σ1,…,σn}I = \{\sigma_1, \dots, \sigma_n\}I={σ1​,…,σn​}，有算法输出 O={y1,…,yn}O = \{y_1, \dots, y_n\}O={y1​,…,yn​}。

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

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

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

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

• 可以提供的信息：点的方向（竞争比为1），点的距离
• 思路：来回走
• 拓展：任何算法都不会小于最优解的9倍，对应的是二倍折返走

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

• 作业里的one bit advice思路：价值是奇数位还是偶数位。竞争比是8/3

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

• 作业里的one bit advice思路：告诉我未来会不会滑雪d次。

页表管理： 页表替换策略

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

Online Scheduling and Load Balancing

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

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

• Positive Result：设计一个在竞争比上比较好的算法
• Negative Result：构造bad example，说明没有online算法能做的更好了
• Best Possible/Optimal Online算法：Matched bounds

k-server Problem

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

• 贪心：来了一个请求后谁近谁去，显然可以构造一个竞争比为无限的例子：

  • 如图所示，如果请求是A, B, C, A, C, A, C, A, C…，竞争比无限

• 离线算法：动态规划；或者可以用费用流，O(kn2)O(kn^{2})O(kn2)

竞争比下界

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

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

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

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

竞争比分析

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

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

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

树上K-Server问题的DC算法：

• 定义服务点的邻居为到该点路径上没有其他服务员的所有服务员，树上DC就是所有的邻居都要动
• 也是一个k-competitive，势能函数定义相同

一般图上的K-server问题：动态规划，在在线情况下可以保证2k−12k-12k−1的竞争比