Introduction to Algorithms/Self-organizing Lists And Competitive Analysis

Video Link

Self-organizing lists

List $L$ of $n$ elem

• Operation Access(x), cost is $\mathrm{rank}_{L}(x)$ = distance of $x$ from head of $L$.
• $L$ can be reordered by transposing adjacent elems, cost is 1.

On-line: A seq $S$ of ops is provided one at a time. For each op, an on-line alg $A$ must execute the op immediately.

Off-line: May see all of $S$ in advance.

Goal. Min total cost $C_{A}(S)$.

Worst-case analysis: Always access the tail elem of $L$, $C_{A}(S)=\Omega(

S

\cdot n)$, not so bad.

Average-case analysis: Suppose elem $x$ accessed with prob $p(x)$.

\[E[C_{A}(S)]=\sum_{x \in L}p(x) \cdot \mathrm{rank}(x)\]

Which is minimized when $L$ is sorted in decreasing order w.r.t. $P$.

Heuristic: Keep count of # times each elem is accessed and maintain list in order of decreasing count.

Pracrice: “Move-to-front” heuristic. After accessing $x$, move $x$ to head of list using transposes, and the cost is $2\mathrm{rank}_{L}(x)$. Responds well to locality in $S$.

Competitive Analysis

• Danny Sleator and Bob Tarjan.

Def. An on-line alg $A$ is $\alpha$-competitive if $\exists$ constant $k$ s.t. for any seq $S$ of ops,

\[C_{A}(S))\leqslant \alpha \cdot C_{opt}(S)+k\]

Opt stands for the optimal offline algorithm.(God’s alg)

Theorem Move-to-front(MTF) is 4-competitive for self-organizing lists.

Proof:

• Let $L_{i}$ be MTF’s list after $i$th access and $L_{i}^*$ be OPT’s …
• Let $c_{i}=$ MTF’s cost of $i$th op = $2rank_{L_{i-1}}(x)$ if it accesses $$. And $c_{i}^{}=$ OPT’s cost for $i$th op $=rank_{L_{i-1}}^(x)+t_{i}$, if OPT transposes $t_{i}$ times.

Define the potential function $\Phi: {L_{i}} \to \mathbb{R}$ by

\[\begin{align} \Phi (L_{i}) &=2|\\{x,y\\}: x\prec_{L_{i}} y \text{ and } y \prec_{L_{i}^*}x| \newline &= 2 \cdot \text{inversions} \end{align}\]

$x \prec y$: $x$ precedes $y$.

Note: $\Phi (L_{i})\geqslant 0 ,\forall i, \Phi(L_{0})=0$ if MTF and OPT start with same list.

How much does $\Phi$ change from one transpose? A transpose creates or destroys one inversion $\implies \Delta \Phi =\pm 2$.

What happens when op $i$ accesses $x$? Define

• $A=\{y\in L_{i-1}: y \prec_{L_{i-1}}x \text{ and } y \prec_{L_{i-1}^*} x\}$
• $B=\{y\in L_{i-1}: y \prec_{L_{i-1}}x \text{ and } y \succ_{L_{i-1}^*} x\}$
• $C=\{y\in L_{i-1}: y \succ_{L_{i-1}}x \text{ and } y \prec_{L_{i-1}^*} x\}$
• $D=\{y\in L_{i-1}: y \succ_{L_{i-1}}x \text{ and } y \succ_{L_{i-1}^*} x\}$

• $r=rank_{L_{i-1}}(x)$ and $r^{}=rank_{L_{i-1}^}(x)$

  \[r=|A|+|B|+1, r^{*}=|A|+|C|+1\]

  When MTF moves $x$ to front, it creates $

  A

  $ inversions and destroys $

  B

  $ inversions. Each transpose by OPT, create $\leqslant 1$ inversion. Thus,

  \[\Phi (L_{i}) - \Phi(L_{i-1}) \leqslant 2(|A|-|B|+t_{i})\]

Amortized cost is

\[\begin{align} \hat{c_{i}} &= c_{i} + \Delta \Phi(L_{i}) \newline &\leqslant 2r+2(|A|-|B|+t_{i}) \newline &= 4|A|+2t_{i}+2 \newline &\leqslant 4(r^{*}+t_{i}) \quad \text{since } r^{*} =|A|+|C|+1 \geqslant |A|+1 \newline &= 4c_{i}^{*} \end{align}\]

Thus, $C_{MTF}(S)=\sum_{i=1}^{n}c_{i}\leqslant \sum_{i=1}^{n}\hat{c_{i}}\leqslant 4\sum_{i=1}^{n}c_{i}^*=4C_{OPT}(S)$.

If we count transposes that move $x$ toward the front of $L$ as “free”. (models splicing $x$ in and out of $L$ in const time), then MTF is 2-competitive.

What if $L_{0}\neq L_{0}^*$? Then $\Phi (L_{0})$ might be $\Theta(n^2)$ worst-case ($n$ is the initial length). Thus $C_{MTF}(S)\leqslant 4C_{OPT}(S)+\Theta(n^2)$, still 4-competitive.