On List Update and Work Function Algorithms(15)

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

15 remain at their original depths. (The speci c de nition of the state T 0 will emerge from the rest of the construction; the cost of the modi ed sequence can be bounded by using only the non-decreasing depth property.) Evaluate k= x in this state T 0 . Using the non-decreasing depth property, we show (Proposition 9, proof deferred to the Appendix) that x(T 0 )+ d(T; T 0 ) x(T )+ jRj+ I T; T 0] (where I X; Y] is de ned as above). 2. Considering O as a sequence of transpositions and references transforming T to S, O: T ! S, apply a suitably chosen subsequence O0, including all of the references and many of the transpositions, of O. This subsequence O0 will transform T 0 to a state S 0 . In this state S 0, (i) each referenced element has the same depth as it does in S; (ii) the element x occupies the position of the frontmost non-referenced element in S; and (iii) all other non-referenced elements in S 0 are in their same respective pairwise order as in S . Evaluate x in S 0 . We show (Proposition 11, proof deferred to the Appendix) that such a transformation from some T 0 with the non-decreasing depth property, to S 0 as so de ned, can be achieved by a suitably chosen subsequence of O. We also show that I T; T 0]+ I T 0; S 0] I T; S], by showing that the interchanges between non-referenced items in the transformations from T to T 0 and from T 0 to

S 0 are all contained in O.^^^ 3. Transform S 0 to the state S, where S is de ned by (i) S"x S, and (ii)^ is the depth of the front-most non-referenced element in S the depth of x in S (which is also its depth in S 0 ). We show (Proposition 10, proof deferred to the Appendix) that x(S 0 )+^ d(S 0; S )+ jNj x(S ). This process can be illustrated as follows, using ! to denote a reference, and; to denote pairwise interchanges between references. The original sequence O has: x x

:::; T?! T;:::; S?! S (Recall that we assume that O satis es x= t in S .)

After the above modi cations (denoted 1, 2, 3), the sequence is:3^ x x 2 O 1:::; T; T 0?! T 0:::; S 0?! S 0; S

The result now follows by comparing the cost of the modi ed sequence to the cost of the original sequence from and after !k?1 (T ). The cost attributable to the original sequence is the sum of 1. x(T ); 2. the cost of references in 2; 3. from T to S, the cost of interchanges between referenced elements; 4. from T to S, the cost of interchanges between a referenced and a nonreferenced element; 5. from T to S, the cost I T; S] of interchanges between non-referenced elements; and 6. x(S ).