# 在线算法

1. 在线算法是指在做决策时对输入没有完全的了解，只能根据过去的信息而对于未来只有部分或没有信息的算法
   - 这些算法尽可能达到和最优离线算法一样好的效果

2. 竞争比：离线算法的最优解与在线算法的解的比值的最坏情况

3. 租雪橇问题
   - 总的滑雪橇天数提前不可知，如果租雪橇，每天花费 1，如果买雪橇，需要花费 B
   - 提前知道总天数，则花费 $\min(T,B)$ 即可
   - 不知道总天数，每天租雪橇，如果租雪橇的总花费达到 B-1，则在第 B 天买雪橇，否则继续租雪橇
   - 竞争比可以达到 2-1/B

4. 丢失的牛问题
   - 已知有一只牛丢了，最后一次看到它在一个丁字路口，不知道是往左走还是往右走了，如何找到这只牛花的时间最少
   - 先向右走，走过路口 1 米后往左走，走过路口 2 米后折返，走过路口 4 米后折返，走过路口 8 米后折返，以此类推，直到走过路口 2^k 米后折返，这样可以保证最多走 2^(k+1)-1 米，如果这时候还没有找到牛，就从路口 2^k 开始向右走，每次走 2^(k-1) 米，直到找到牛
   - 竞争比为 9
   - 最坏情况为右侧 $2^j+\varepsilon$
   - 使用在线算法花费时间 $2(1+2+\cdots+2^{j+1})+2^j+\varepsilon<9\cdot 2^j$，因此竞争比不到 9

5. 秘书问题
   - 有 $n$ 个秘书，每个秘书都有一个随机的能力值，要从中选出一个秘书，如果不选，就不能再选，如何选出能力值最高的秘书
   - 先让前 $n/e$ 个秘书来面试，如果都不选，就选第一个能力值超过前 $n/e$ 个秘书的秘书，如果都不选，就选最后一个，这样可以保证选到最好的秘书的概率为 $1/e$

6. 任务调度问题
   - 有 $m$ 个相同的机器，一系列处理时间 $p_1,p_2,\ldots$ 的任务，要求每个任务都分配到一个机器上，每个机器某时刻只能执行一个任务，如何安排任务，使得每台机器上的最大任务执行时间最小 makespan=$\max_i\sum_{j on M_i}p_j$
   - 总是把到来的任务放在当前负载最小的机器上，这样可以保证 makespan 不超过最优解的 2 倍

7. 页内存替换算法

> APX, 有常数近似解
> APX-hard，无法做到比常数近似更好