5
$\begingroup$

Preparing for my finals in my "advances algorithms" course. Usually there is a question to prove one of the theorems that was given over the course. I'm currently trying to write a full proof of the following statement:

Self-organizing list that uses Move-to-Front is 2-Competitive.

For the completeness of the question:

Move to Front (MF): move element to the head of the list after each operation on that element.

For that, I follow the "Amortized Efficiency Of List Update and Paging Rules" papier by DANIEL D. SLEATOR and ROBERT E. TARJAN. Basically I'm trying to prove their first theorem:

For any given algorithm $A$ that solves the dictionary problem and input $\vec{S}=s_{1},\ldots,s_{m}$ on empty set, we get: $$ C_{\text{MF}}\left(\vec{S}\right)\leq2C_{A}\left(\vec{S}\right)+X_{A}\left(\vec{S}\right)-F_{A}\left(\vec{S}\right)-m $$ where:

  • $C_{Z}\left(\vec{S}\right)$ is cost function of algorithm $Z$ on input $\vec{S}$.
  • $X_{Z}\left(\vec{S}\right)$ is the number of paid exchanges of algorithm $Z$ on input $\vec{S}$.
  • $F_{Z}\left(\vec{S}\right)$ is the number of free exchanges of algorithm $Z$ on input $\vec{S}$.

The papier is great but I feel it skips a lot of steps in their solution. I'm trying to re-write the proof but without skipping any steps. Here is what I did:

By using the potential method, the potential function $\Phi$ will be defined as the number of inversions $(i,j)$ whose order of appearance in the list based on algorithm $\text{MF}$ is different from the order of their appearance in list based on algorithm $A$. That is, the potential function will count the pairings $(i,j)$ in which $i$ appears before $j$ in an $A$-based list and after $j$ in a $\text{MF}$-based list or $i$ appears before $j$ in a $\text{MF}$-based list and after $j$ in an $A$-based list. The potential function treats pairs in an unordered manner, meaning that the pair $(i,j)$ is the same as the pair $(j,i)$.

We start from two empty lists, so at the beginning of the series of operations, the potential is $\Phi\left(D_{0}\right)=0$. Also, for all $l$ the potential is positive, since $\Phi\left(D_{l}\right)\geq\Phi\left(D_{0}\right)=0$ holds.

We will analyze the amortized time of the $\text{MF}$ algorithm for each operation $s_{l}$ as a function of the cost of the operation in algorithm $A$. We will first discuss the search operation of element $i$. Without limiting generality, let's assume that the $A$-based list consists of the elements $1,2,3,\ldots,i,i+1,\ldots$ (this assumption is possible because it can be obtained by changing the names of the elements in lists based on $A$ and $\text{MF}$).

Let $x_{i}$ be the number of members $j$ that hold $i<j$ and are before $i$ in the list based on $\text{MF}$ (before the operation $s_{l}$). Since we assume an order in which the $j$-th member in the list based on $A$ is $j$, we will get that $x_{i}$ is the number of members $j$ that appear after $i$ in the based list $A$ and before $i$ in the based list $\text{MF}$. In addition, let $k$ be the index of member $i$ in the based list $\text{MF}$. Therefore, out of $k-1$ members preceding member $i$ in the list based on $\text{MF}$, $x_{i}$ of which do not precede $i$ in the based list $A$ and exactly $k-1-x_{i}$ also precede $i$ in the based list $A$.

According to the $\text{MF}$ algorithm, it follows that after performing the $s_{l}$ operation, element $i$ is moved to the top of the $\text{MF}$-based list. We will separate cases according to the types of pairs $(i,j)$:

  • Assume that before the move, $j$ appeared before $i$ in both lists. Therefore, after the move, $j$ will appear after $i$ in a list based on $\text{MF}$ and before $i$ in a list based on $A$. Since $x_{i}$ is the number of members of $j$ that satisfy $i<j$ and are before $i$ in a list based on $\text{MF}$ before the operation $s_{l}$ follows $\Phi\left(D_{l-1}\right)=x_{l}$. In this case, after performing the $s_{l}$ operation, $i$ is moved to the top of the $\text{MF}$ based list. Therefore, $k-1-x_{i}$ elements that appeared before $i$ in both lists, now appear after $i$ in the $\text{MF}$ based list and before $i$ in the $A$ based list. Also, $x_{i}$ elements that appeared before $i$ in the $\text{MF}$ and after $i$ in the based list $A$, now appear after $i$ in both lists. Thus $\Phi\left(D_{l}\right)=k-1-x_{i}+y$ where $y$ is the contribution of the paid operations and the free operations. We will divide into sub-cases:
    • Assume that $X_{A}(l)=0$ and $F_{A}(l)=0$. $X_{A}(l)=0$ holds and therefore no paid operation was performed. Also, $F_{A}(l)=0$ holds and therefore no free operation was performed. In this case, we get $y=0$, i.e. $\Phi\left(D_{l}\right)=k-1-x_{i}$. It follows that the change in potential is: $$ \Delta\Phi=\Phi\left(D_{l}\right)-\Phi\left(D_{l-1}\right)=\left(k-1-x_{i}\right)-x_{ i}=k-1-2x_{i} $$ The actual cost of this operation is $c_{l}=k$ and therefore we get: $$ \hat{c}_{l}=c_{l}+\Phi\left(D_{l}\right)-\Phi\left(D_{l-1}\right)=c_{l}+\Delta \Phi=k+\left(k-1-2x_{i}\right)=2\left(k-x_{i}\right)-1 $$ Since there are $k-1$ elements prior to $i$ in a list based on $\text{MF}$ and only the elements $\{1,2,\ldots,i-1\}$ do not contribute to $x_{i}$ (the rest of the elements necessarily contribute to $x_{i}$), it follows that $x_{i}\geq k-i$ holds. From this it follows that $k-x_{i}\leq i$ holds and therefore we get: $$ \hat{c}_{l}=2\left(k-x_{i}\right)-1\leq2i-1=2i+0-0-1 $$ Since $C_{A}(l)=i, X_{A}(l)=0$ and $F_{A}(l)=0$ hold, we get: $$ \hat{c}_{l}\leq2i+0-0-1=2C_{A}(l)+X_{A}(l)-F_{A}(l)-1 $$
    • Assume that $X_{A}(l)=r$ and $F_{A}(l)=0$. $X_{A}(l)=r$ holds and therefore a paid operation was performed in which member $i$ was moved $r$ places down the list (and the pass with member $i+r$). Also, $F_{A}(l)=0$ holds and therefore no free operation was performed. In this case, we get $y=r$, i.e. $\Phi\left(D_{l}\right)=k-1-x_{i}+r$. It follows that the change in potential is: $$ \Delta\Phi=\Phi\left(D_{l}\right)-\Phi\left(D_{l-1}\right)=\left(k-1-x_{i}+r\right)- x_{i}=k-1+r-2x_{i} $$ The actual cost of this operation is $c_{l}=k$ and therefore we get: $$ \hat{c}_{l}=c_{l}+\Phi\left(D_{l}\right)-\Phi\left(D_{l-1}\right)=c_{l}+\Delta \Phi=k+\left(k-1+r-2x_{i}\right)=2\left(k-x_{i}\right)+r-1 $$ Since there are $k-1$ elements prior to $i$ in a list based on $\text{MF}$ and only the elements $\{1,2,\ldots,i-1\}$ do not contribute to $x_{i}$ (the rest of the elements necessarily contribute to $x_{i}$), it follows that $x_{i}\geq k-i$ holds. From this it follows that $k-x_{i}\leq i$ holds and therefore we get: $$ \hat{c}_{l}=2\left(k-x_{i}\right)+r-1\leq2i+r-1=2i+r-0-1 $$ Since C_{A}(l)=i, X_{A}(l)=r and F_{A}(l)=0 hold, we get: $$ \hat{c}_{l}\leq2i+r-0-1=2C_{A}(l)+X_{A}(l)-F_{A}(l)-1 $$
    • Assume that $X_{A}(l)=0$ and $F_{A}(l)=r$. $X_{A}(l)=0$ holds and therefore no paid operation was performed. Also, $F_{A}(l)=r$ holds and therefore a free operation was performed in which member $i$ was moved $r$ places down the list. In this case, we get $y=-r$, i.e. $\Phi\left(D_{l}\right)=k-1-x_{i}-r$. It follows that the change in potential is: $$ \Delta\Phi=\Phi\left(D_{l}\right)-\Phi\left(D_{l-1}\right)=\left(k-1-x_{i}-r\right)- x_{i}=k-1-r-2x_{i} $$ The actual cost of this operation is $c_{l}=k$ and therefore we get: $$ \hat{c}_{l}=c_{l}+\Phi\left(D_{l}\right)-\Phi\left(D_{l-1}\right)=c_{l}+\Delta \Phi=k+\left(k-1+r-2x_{i}\right)=2\left(k-x_{i}\right)-r-1 $$ Since there are $k-1$ elements prior to $i$ in a list based on $\text{MF}$ and only the elements $\{1,2,\ldots,i-1\}$ do not contribute to $x_{i}$ the rest of the elements necessarily contribute to $x_{i}$), it follows that $x_{i}\geq k-i$ holds. From this it follows that $k-x_{i}\leq i$ holds and therefore we get: $$ \hat{c}_{l}=2\left(k-x_{i}\right)-r-1\leq2i-r-1=2i+0-r-1 $$ Since $C_{A}(l)=i, X_{A}(l)=0$ and $F_{A}(l)=r$ hold, we get: $$ \hat{c}_{l}\leq2i+0-r-1=2C_{A}(l)+X_{A}(l)-F_{A}(l)-1 $$
  • Assume that before the move $j$ appeared after $i$ in both lists. So after the move, $j$ will still appear after $i$ in both lists. Since $x_{i}$ is the number of members $j$ that satisfy $i<j$ and are before $i$ in the list based on $\text{MF}$ before the operation $s_{l}$ follows $\Phi\left(D_{l-1}\right)=x_{l}$. ???
  • Assume that before the move $j$ appeared before $i$ in the $\text{MF}$ based list and after $i$ in the $A$ based list. Therefore after the move, $j$ will appear after $i$ in both lists. Since $x_{i}$ is the number of members $j$ that satisfy $i<j$ and are before $i$ in the list based on $\text{MF}$ before the operation $s_{l}$ follows $\Phi\left(D_{l-1}\right)=x_{ l}$. ???
  • Suppose that before the move $j$ appeared after $i$ in the $\text{MF}$-based list and before $i$ in the $A$-based list. Therefore, after the move, $j$ will appear after $i$ in the $\text{MF}$-based list and before $i$ in the $A$-based list. Since $x_{i}$ is the number of elements $j$ that hold $i<j$ and are before $i$ in the list based on $\text{MF}$ before the operation $s_{l}$ follows $\Phi\left(D_{l-1}\right)=x_{l}$. ??

We have proved that for a search operation holds: $$ \hat{c}_{l}\leq2C_{A}(l)+X_{A}(l)-F_{A}(l)-1 $$ In an almost identical way, this claim can be proved for insertion and deletion operations. In this way, the correctness of the claim for each action is proven. It remains to sum up the costs into fractions $\hat{c}_{l}$ and thus obtain a block on the total running time $C_{\text{MF}}\left(\vec{S}\right)$ of the $\text{MF}$ algorithm using the running time of algorithm $A$: $$ C_{MF}\left(\vec{S}\right) =\sum_{l=1}^{m}c_{l}\leq\sum_{l=1}^{m}\hat {c}_{l}\leq\sum_{l=1}^{m}\left(2C_{A}(l)+X_{A}(l)-F_{A}(l)-1\right ) =2C_{A}\left(\vec{S}\right)+X_{A}\left(\vec{S}\right)-F_{A}\left(\vec{S}\right)-m $$ We got that the total running time $C_{\text{MF}}$ of algorithm $\text{MF}$ is blocked by twice the running time $C_{A}+X_{A}$ of algorithm $A$, as required.

I was managed to write a proof for the first case where "that before the operation, $j$ appeared before $i$ in both lists". I managed to do so because in the original papier and other resources online, they talk only about this case. I guess this is because it should be also identical for other cases. But it feels like really difference cases that affect the whole structure of those lists. So to summarize, I have the following requests:

  • Please help me finish the proof for the three other cases. It should not be formal - all I need is to know what should be $\Phi\left(D_{l}\right)$ and how to explain it. I just need to understand what should be the values of all the parameters in each case so I could get to the right formula.
  • Why there is no subcase where $X_{A}(l)=r$ and $F_{A}(l)=r$. Isn't it possible? I didn't see it in other proofs.
  • If there are mistakes in my proof, please point them out so I could fix them.
$\endgroup$
2
  • 2
    $\begingroup$ This seems like too much for a single question on Stack Exchange. Checking a multi-page proof is beyond the scope of this site. Our site works best for narrowly focused questions that will be useful to others in the future. Also, "please help me finish three other cases" is too much -- each post here should be a single focused question. I see about four or five questions here (each of the three cases in your first bullet item; your second bullet item; and a request to check for mistakes). $\endgroup$
    – D.W.
    Aug 6, 2022 at 19:25
  • 1
    $\begingroup$ Maybe you might can summarize your current proof or just give a short proof idea since you are also asking for proof idea for the other cases? $\endgroup$
    – Russel
    Aug 10, 2022 at 8:40

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.