在线算法
理论
定义 1： 一个优化问题 Π由一组的情况下， ＆Sigma; Π 。对于每一个实例σ∈Σ Π 有一组Ζ σ 的解决方案和一个目标函数 ˚F σ ：Ζ σ →交通ℜ ≥0 其中分配 apositive 真实值的每一个的解决方案。
我们说 OPT（σ）是最优解的值，A（σ）是算法 A 对于问题Π和 w A （σ）= fσ （A（σ））其值的解。
定义 2： 最小化问题的在线算法 A 如果存在常数τ∈ℜ，则竞争比率 r≥1
w A （σ）= fσ （A（σ））≤r⋅OPT（＆sigma）+τ
所有实例σ∈Σ Π 。A 称为 r 竞争在线算法。甚至
w A （σ）≤r⋅OPT（＆sigma）
所有实例σ∈Σ Π 则称 A 是一个严格的 R-竞争力的在线算法。
命题 1.3： LRU 和 FWF 是标记算法。
证明： 在每个阶段的开始（第一个阶段除外）， FWF 具有缓存未命中并清除缓存。这意味着我们有 k 个空页面。在每个阶段都要求最多 k 个不同的页面，因此在阶段期间将会出现逐出的情况。所以 FWF 是一种标记算法。
让我们假设 LRU 不是标记算法。然后有一个实例σ，其中 LRU 在阶段 i 中被标记的页面 x 被驱逐。让σ 吨 在阶段 I，其中 x 被逐出该请求。由于 x 被标记，因此在同一阶段中 x 必须有较早的请求σt * ，因此 t * <t。T *之后，x 是最新的缓存页面，所以要在 t 序列σ得到了拆迁户 T * + 1 ，…，σ ŧ 必须从 x 个不同的页面请求至少 k。这意味着阶段 i 已经请求至少 k + 1 个不同的页面，这与阶段定义相矛盾。因此 LRU 必须是标记算法。
命题 1.4： 每个标记算法都是严格的 k 竞争性。
证明： 设σ是寻呼问题的实例和σ的相位数。当 l = 1 则则每个标记算法都是最优的并且最优离线算法不能更好。
我们假设 l≥2。例如σ的每个标记算法的成本是从上面用 l·k 限制的，因为在每个阶段中，标记算法在不驱逐一个标记页面的情况下不能超过 k 个页面。
现在我们试图表明，最优离线算法在第一阶段中为σ，k 驱逐了至少 k + 1-2 页，并且除了最后一阶段之外每个后续阶段至少有一个。为了证明，我们定义σ的 l-2 析取子序列。子序列 i∈{1，…，l-2}从阶段 i + 1 的第二个位置开始，并以阶段 i + 2 的第一个位置结束。
设 x 为阶段 i + 1 的第一页。在子序列 i 的开始处，在最佳离线算法高速缓存中存在页面 x 和至多 k-1 个不同页面。在子序列中，我的 k 页面请求与 x 不同，因此最佳离线算法必须为每个子序列驱逐至少一页。由于在阶段 1 开始缓存仍为空，因此最佳离线算法在第一阶段期间导致 k 驱逐。这表明了这一点
w A （σ）≤l⋅k≤（k + l-2）k≤OPT（σ）·k
推论 1.5： LRU 和 FWF 是严格 K-竞争力。
对于在线算法 A 是否具有竞争力，我们称之为 A 不具有竞争力。
命题 1.6： LFU 和后进先出法是没有竞争力。
证明： 设 l≥2 常数，k≥2 缓存大小。不同的缓存页面是 nubered 1，…，k + 1。我们看看以下顺序：
第 1 页要求第 1 页，而不是第 2 页，因此要求第 1 页。最后，对页面 k 和 k + 1 存在（l-1）交替请求。
LFU 和 LIFO 用 1-k 页填充缓存。当请求页面 k + 1 时，页面 k 被逐出，反之亦然。这意味着子序列（k，k + 1） l-1 的 每个请求都会驱逐一页。此外，它们是第一次使用第 1-（k-1）页时的 k-1 缓存未命中。所以 LFU 和 LIFO 逐出大致的 k-1 + 2（l-1）页面。
现在我们必须证明，对于每个常数τ∈ℜ和每个常数 r≤1，存在一个 l
等于
为了满足这种不相等，你必须选择足够大的。所以 LFU 和 LIFO 没有竞争力。
命题 1.7： 有没有 R-中的竞争与寻呼确定性在线算法 [R <K 。
来源
基本材料
- 脚本在线算法（德语），Heiko Roeglin，波恩大学
- 页面替换算法
进一步阅读
- Allan Borodin 和 Ran El-Yaniv 的在线计算和竞争分析