個人讀書筆記，歡迎大家批評指正、交流
An Introduction to Online Computation
Authors Komm, Dennis

文章目錄

• 1 Introduction
• • 1.1 Offline Algorithms
  • 1.2 Online Algorithms and Paging
  • • Online Problem
    • Online Algorithms
    • Competitive Ratio
    • Theorem 1.2，1.3
    • Paging
    • $pageingproblem$
  • 1.3 An Upper Bound for Paging
  • • $k?$Phase Partition
    • Theorem 1.4 Fifo is strictly k-competitive for paging
  • 1.4 A Lower Bound for Paging：k-compititive
  • • Theorem 1.5 No online algorithm for paging is better than k-compititive?
    • Theorem 1.6 LIFO is not competitive for paging
    • Theorem 1.7 LFU（使用頻率最低） is not competitive for paging
  • 1.5 Marking Algorithms
  • • Theorem 1.8. Every marking algorithm is strictly $k$-competitive for paging
    • Theorem 1.9. LRU is a marking algorithm
  • 1.6 Refined Competitive Analysis
  • • lookahead
    • • No online algorithm with lookahead $?$ for paging is better than $k$ competitive.
    • resource augmentation
    • • (h,k)-paging problem
    • Every marking algorithm is k/(k-h+1)-competitive for (h,k)-paging
    • Every marking algorithm is k/(k-h+1)-competitive for (h,k)-paging

1 Introduction

Online computation, that is, algorithms that work on problem instances which they do not know from the start, but that get revealed piece by piece. These algorithms are called online algorithms, and they are commonly analyzed using so-called competitive analysis, which compares their solution to an optimal one.

在線計算，也就是在問題實例上工作的算法，這些問題實例他們從一開始并不知道，但逐漸顯露出來。這些算法被稱為在線算法，通常使用所謂的競爭分析來分析它們，將它們的解與最優(yōu)解進行比較。

1.1 Offline Algorithms

停機問題，P,NP,NPC,NP-hard,優(yōu)化問題的定義

近似算法：

對于最大化問題：

? $gain(OPT(I))\le r?gain(gain(I))$,

? $\frac {gain(OPT(I)) } { gain(ALG(I))} \le r $

對于最小化問題：

? $cost(ALG(I))\le r?cost(ALG(I))$,

? $\frac {cost(ALG(I)) } { cost(OPT(I))}\le r $

背包問題

1.2 Online Algorithms and Paging

Online Problem

? problem:$\Pi$

? instances:$\mathcal{I}$

? solutions:$\mathcal{O}$

? instance: $I\in \mathcal{I}$ is a sequence of $requests$ $I=(x_1,x_2,...,x_n)$

? output: $O\in\mathcal{O} $is a sequence of $answers$ $O=(y_1,y_2,...,y_n)$

? $n\in {\mathbb{N}}^{+}$,i.e. all instances and solutions are finite

? $onlineminimizationproblem$:

? $cost(I,OPT(I))=mincost(I,O)|O\in sol(I)$

? $onlinemaximizationproblem$:

? $gain(I,OPT(I))=maxgain(I,O)|O\in sol(I)$

only knows a prefix of the input in every given time step,只知道之前的輸入

makes decisions that are based only on this knowledge, and，只基于已經(jīng)知道的知識做決策

may not revoke any decision it already made.不能改變之前的決策

Online Algorithms

? Online problem : $\Pi$

? An instance of $\Pi$: $I=(x_1,x_2,...,x_n)$

? An $onlinealgorithm$ ALG for $\Pi$ computes the output $ALG(I)=(y_1,y_2,...,y_n)$, where $y_i$ only depends on $x_1,x_2,...,x_i$,and $y_1,y_2,...,y_{i?1}$, $ALG(I) $is a feasible solution for $I$,that is , $ALG(I)\in sol(I)$.

Competitive Ratio

? Online problem : $\Pi$

? Online algorithm : $ALG$

? For $c\ge 1$,$ALG$ is $c?competitive$ for $\Pi$ if there is a non-negative constant $\alpha$ such that, for every instance $I\in \mathcal{I}$,

? for an online maximization problem,

? $gain(OPT(I))\le r?gain(gain(I))+\alpha$,

? for an online minimization problem,

? $cost(ALG(I))\le r?cost(ALG(I))+\alpha$,

if $\alpha =0$, we call $ALGstrictlyc?competitive$ ,$ALG$ is called if it is strictly 1-competitive.

$c_{ALG}$

$strongly{c}_{ALG}?competitive$

近似比和競爭比考慮的都是當(dāng)前算法的$worst?case$

$competitiveanalysis$

As with the approximation ratio, the competitive ratio is not necessarily constant, but may be a function of the input length $n$ .We use the following terminology. 競爭比不一定是一個常數(shù)，可能是與輸入長度n有關(guān)的函數(shù)

$notcompetitive$ :如果在線算法不具有與輸入長度無關(guān)的競爭比的上界???

即，算法的上界，應(yīng)該與輸入長度無關(guān)，這樣才能是competitive的

$\alpha$這個常數(shù)是必不可少的

Theorem 1.2，1.3

? 對于最小化/最大化問題，there is no online algorithm that is "better than $c?competitve$"

Paging

$phases$:consist of a number of consecutive(連續(xù)的) time steps.

c是任何分頁在線算法競爭比的下界

$pageingproblem$

? minimization

? In memory: $p_1,...,p_m$

? Instance: $I=(x_1,x_2,...,x_n)$, such that $x_i\in \{p_1,...,p_m\}$

? $x_i$is requested in time Step $T_i$,

$ALG$ for paging maintains a cache memory of size $k$ with $k<m$ .

time step $T_i$,cache 中存的東西:$B_i=\{p_{j1},p_{j2},...,p_{jk}\}$

$B_0=\{p_1,p_2,...,p_k\}$

如果$T_i$請求的page在$B_{i?1}$中，命中，cost=0，如果不在，選一個$y_i$置換出去，$ALG$ outputs $y_i=p_j$

cost($ALG(I)$)=|{$i|y_i=0$}|,下標(biāo)是集合的大小？

the goal is to minimize this number.

$demandpagingalgorithms$:每次只替換出一頁，請求分頁算法

Strategies：FIFO，LIFO，LFU(使用頻率最低)，LRU，FWF（flush when full）,LFD(離線算法，remove 之后最晚被請求的)

1.3 An Upper Bound for Paging

這里是在算上界，也就是說，求$cost(ALG(I))$max,和$cost(OPT(I))$min

先介紹些東西，以便于證明上界。

在上一節(jié)中，我們定義了一個在線算法是競爭的，如果它的競爭比c是與輸入長度相關(guān)的一個常數(shù)。

在分頁問題中，c與k,m相關(guān)？

$k?$Phase Partition

k步劃分，針對輸入，而不針對算法

instance：$I=(x_1,x_2,...,x_n)$

A 𝑘-phase partition of 𝐼 assigns the requests from 𝐼 to consecutive disjoint phases 𝑃1, 𝑃2, . . . , 𝑃𝑁 such that

段$P_1$開始于第一個不在最初緩存的被請求的頁面。$P_1$包含I的最大長度子序列，最多包含k個不同的頁面

對于第k個還是第k+1個的說明：
不是說探測到第k個不同的頁面就結(jié)束了，萬一之后的還都是與之前重復(fù)的呢？所以是遇到第k+1個不同的頁面之前

$P_2$~$P_N$是$I$的最大子序列，從$P_{i?1}$開始，最多是k個不同的頁面

$P_{i+1}$中的第一個請求頁面，不同于$P_i$中的所有頁面

觀察在右移之后的$P_i^{{}^{\prime }}$,與$P_i^{{}^{\prime }}$開始之前請求的最后一個頁面相比，有k個不同的頁面，

Theorem 1.4 Fifo is strictly k-competitive for paging

對于$P_i,(1\le i\le N)$，最多引起$k$次page fault

設(shè)$p$是$P_i$中第一個引起fault的頁面，所以要把$p$緩存進cache，此時cache中，在$p$前面還有k-1個與p不同的頁面，所以在之后的k-1次置換中，$p$一直都在cache中，而在$P_i$中，除了$p$也就還剩下k-1個不同的頁面，所以during $P_i$，沒有能夠引起兩次fault的頁面，因此，對于$P_i,(1\le i\le N)$，最多也就引起$k$次page fault

對于$N$個$P$,最多引起$N?k$次fault

$OPT(I)$has to make at least one page fault for every phase.

考慮example1.3

input:

cache的初始狀態(tài)：$(p_1,p_2,p_3,p_4,p_5)$

然后用phase表示一下：

再移動一下，以便于分析，

考慮一般情況，首先，$x_i$是第一個引起fault的(就是從$P_1$移動到$P_1^{{}^{\prime }}$的時候移出去的，$P_1$的定義就是以第一個fault開頭的)

對于$P_i^{’},1\le i\le N-1 $,$P_{i-1}^{{’}$中最后一個頁面$p}{’}$，在$P_i^{{’}$開始之前，$p}{’}$一定在cache中，但是$P_i^{{’}$中還有與$p}{’}$不同的k個頁面呢，就算cache中其余k?1個位置存的都是$P_i^{’}$中所需要的頁面，那至少也要fault一次了，因此，$P_i^{’},1\le i\le N-1 $，每個1次，一共就是$N-1$次，再加上$x_i$，一共就是$N$次。

$P_N$是一定不產(chǎn)生fault，還是說是為了計算at least給舍去了？，我覺得是給舍去了

綜合1.和2.，計算得到

$$\frac{cost(ALG(I))}{cost(OPT(I))}=\frac{N?k}{N}=k$$

//這里是在算上界，也就是說，求$cost(ALG(I))$max,和$cost(OPT(I))$min？？？？

1.4 A Lower Bound for Paging：k-compititive

這里是在算下界，也就是說，求$cost(ALG(I))$min,和$cost(OPT(I))$max？

有沒有比FIFO,FWF,LRU更好的在線算法呢？沒了

在考慮$worst?case$的情況下，至少也是$OPT$的$k$倍

adversary（對手，敵人） V.S. $ALG$

adversary想讓$cost(ALG(I))$越大越好，這樣競爭比也就更大了

我們考慮一個請求分頁問題（每次只置換一個，滿了才置換）

Theorem 1.5 No online algorithm for paging is better than k-compititive?

adversary（對手）構(gòu)造的實例，總是知道ALG想替換出什么，然后ALG就總是fault，

OPT就選擇成LFD，是一個離線算法，總是能替換出之后不需要的page

分段，然后分析

$cost(ALG(I))=n=c?k$

$cost(OPT(I))\le c$?

$\frac{cost(ALG(I))}{cost(OPT(I))}\ge k$?

$cost(ALG(I))=n=c?k$

如果$cost(OPT(I))$是常數(shù)，那么競爭比就是n了，那就not competitive（如果隨著n的增長而增長，根據(jù)[定理1.2](#Theorem 1.2，1.3),可知沒有比k更小的競爭比）

如果競爭比是常數(shù)，就是competitive，如果競爭比隨著n按比例變化，就是not competitive

Theorem 1.6 LIFO is not competitive for paging

memory的大小是$m$，即一共有$m$個頁面

cache的大小是$k$，即一種只能在緩存中存$k$個頁面

cache中初始化為
$$\{p_1,p_2,...,p_k\}$$
To this end,為此構(gòu)造實例,實例長度為n
$$\{p_{k+1},p_i,p_{k+1},p_i,p_{k+1},p_i,p_{k+1},p_i,...\}$$

$cost(LIFO(I))=n$

$cost(OPT(I))=1$

Theorem 1.7 LFU（使用頻率最低） is not competitive for paging

就也是構(gòu)造一個實例，然后來證明這是not competitive的

1.5 Marking Algorithms

This class of algorithms plays an important role in the context(環(huán)境) of randomized computation for paging.

Marking Algorithm：

開始處理請求之前，所有的都標(biāo)記

分段工作，標(biāo)記已經(jīng)被請求過的pages，只替換沒被標(biāo)記過的

如果全都標(biāo)記過了，還發(fā)生了一次page fault，結(jié)束當(dāng)前phase，

取消所有標(biāo)記，開始新的phase

concept，概念

Theorem 1.8. Every marking algorithm is strictly $k$-competitive for paging

Theorem 1.9. LRU is a marking algorithm

To prove the claim means to show that Lru never removes a page that is
currently marked by some marking algorithm.

For a contradiction,矛盾

反證法

$P_i$中只能至多有$k$個不同的page,因為是 $k?phase$ partition

證明出現(xiàn)矛盾:$P_i$出現(xiàn)k+1個page

https://riptutorial.com/algorithm/example/25916/paging–online-caching-

FWF is also a marking algorithm

LFU and LIFO is no marking algorithm,and not competitive

FIFO is no marking algorithm,but strictly k-competitive

1.6 Refined Competitive Analysis

Refined,細致的，精確的

lookahead

with lookahead $?$,$AL{G}_{?}$ sees the current request together with the subsequent $?$ requests

adversary對手依舊是知道$AL{G}_{?}$ 的工作流程，也知道$?$，

such that，如此…以致于

No online algorithm with lookahead $?$ for paging is better than $k$ competitive.

找下界，盡量讓$AL{G}_{?}$少發(fā)生page fault

give an instance $I$
$$(p_{k+1},\begin{array}{c}{p}_{k+1},?,p_{k+1}\\ ?requests\end{array},p_i,\begin{array}{c}{p}_i,?,p_i\\ ?requests\end{array},?)$$
$AL{G}_{?}$只能知道前面$?$個，按照上述instance，$AL{G}_{?}$每$?+1$個page，fault一次，所以$cost(AL{G}_{?})=\frac{n}{??1}$

$OPT$的話，求的是opt的最壞情況。causes at most one page fault every $k(?+1)$ time steps.$cost(OPT)=\frac{n}{k(??1)}$
$$\frac{cost(AL{G}_{?}(I))}{cost(OPT(I))}=\frac{\frac{n}{??1}}{\frac{n}{k(??1)}}=k$$

resource augmentation

online algorithm v.s. adversary

(h,k)-paging problem

$OPT$ is only allowed to use a size of $h\le k$ for the same input.

Every marking algorithm is k/(k-h+1)-competitive for (h,k)-paging

本章最重要的就是那個

$k$-phase partition

$cost(ALG)=k?N$

$cost(OPT)=(k?(h?1))?(N?1)+1$

最后不一定是加一，可以忽略不記，主要是要明確，在(h,k)-paging中，$0<\alpha \le k$
$$competitiveratio=\frac{k}{k?h+1}$$

$$k?N\le \frac{k}{k?h+1}?((k?(h?1))?(N?1)+1)+\alpha$$

of $h\le k$ for the same input.

Every marking algorithm is k/(k-h+1)-competitive for (h,k)-paging

本章最重要的就是那個

$k$-phase partition

$cost(ALG)=k?N$

$cost(OPT)=(k?(h?1))?(N?1)+1$

最后不一定是加一，可以忽略不記，主要是要明確，在(h,k)-paging中，$0<\alpha \le k$
$$competitiveratio=\frac{k}{k?h+1}$$

$$k?N\le \frac{k}{k?h+1}?((k?(h?1))?(N?1)+1)+\alpha$$

總結(jié)

以上是生活随笔為你收集整理的online-section1-new的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。