On List Update and Work Function Algorithms(16)

Abstract. The list update problem, a well-studied problem in dynamic data structures, can be described abstractly as a metrical task system. In this paper, we prove that a generic metrical task system algorithm, called the work function algorithm, has cons

16 The cost attributable to the modi ed sequence O0 is the sum of 1. from T to T 0, the cost of all interchanges; 2. x(T 0 ); 3. the cost of references in 2; 4. from T 0 to S 0, the cost of interchanges between referenced elements; 5. from T 0 to S 0, the cost of interchanges between a referenced and a nonreferenced element; 6. from T 0 to S 0, the cost I T 0; S 0] of interchanges between non-referenced elements; 7. x(S 0 ); and^ 8. from S 0 to S, the cost of all interchanges. By construction, items two, three and four for the sequence O are identical to items three, four and ve for the sequence O0 . Thus we compare x(T )+ I T; S]+^ x(S ) for the rst sequence to d(T; T 0)+ x(T 0 )+ I T 0; S 0]+ x(S 0 )+ d(S 0; S ) for the second sequence. Given x(T 0 )+ d(T; T 0 ) x(T )+ jRj+ I T; T 0] (Proposition 9), I T; T 0]+^ I T 0; S 0] I T; S] (Proposition 11), and x(S 0 )+ d(S 0; S )+ jNj x(S ) (Proposition 10), the result follows by substitution. t u We obtain the following corollary to Lemma 2. Corollary 2. Consider a request sequence where the last request (the t-th request in ) is to x. If s is wfa-eligible after executing, then the depth of x in s is at most 2jRj, where R is the set of elements that have been referenced since the penultimate reference to x. Proof. Let f be a fundamental state such that !t+1 (s)= !t+1 (f )+ d(f; s). By Proposition 5, f is also wfa-eligible and x(f )= x(s). Suppose x(s)> 2jRj. Then x(f )> 2jRj. Elements in front of x in f either have or have not been referenced since the penultimate reference to x; so x(f )> 2jRj implies jNj> jRj, where N is the set of elements in front of x in f that have not been referenced since the^ penultimate reference to x. Then by Lemma 2 there exists f^ with !t (f )< !t (f )

t u and f"x f^, contradicting the assumption that f is wfa-eligible. Finally, we use the lemma to obtain the main theorem. Theorem 2. WFA0 is O(1) competitive. Proof. Consider an arbitrary element x, and let= 0; x; 1; x; 2; x, where in 1 and 2 there are no references to x. Then by Lemma 2 the depth of x in the Mtm! state, immediately before the nal reference to x, is at most 2r1+ r2, where r1 is the number of distinct elements referenced in 1 and r2 is the number of distinct elements referenced in 2, not referenced in 1, that are moved in front of x at some point during the subsequence 2 . As usual, let G be the number of elements greater than x immediately before its nal reference and let I be the number of elements incomparable to x immediately before its nal reference. In addition, let L(0) be the number of elements