On List Update and Work Function Algorithms(19)

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

19Proof. If the rst non-referenced element in T is x itself, then in order to satisfy the non-decreasing depth property, p(T 0)= p(T ) for all non-referenced elements, and there is nothing to prove. Otherwise, denote by p1;:::; pN the nonreferenced elements in their order in T, with pz= x. We note that for i> z, the non-decreasing depth property requires pi (T )= pi (T 0 ). We start by moving x forward to the location of the rst non-referenced element, p1 . These interchanges all involve x. Next, we move p1 to location 2.10 By the non-decreasing depth property, either p1 or p2 must occupy location 2. If p2 is x, we are done. Otherwise, there may be one interchange, between p1 and p2 . Inductively, at step i, for location i, each referenced element below location i has interchanged with at most one non-referenced element, and each referenced element above location i has not interchanged with any non-referenced elements; and some element pj; j< i, is either (i) adjacent to pi, or (ii) is in location i and pi is x. If the latter, we are done. If the former, one or the other of pi and pj must occupy location i by the non-decreasing depth property; swap them if necessary; and interchange the other with all referenced elements between location i and location i+ 1. By induction, each referenced element has interchanged with at most one non-referenced element, so the number of such interchanges is bounded by the number of referenced elements. The result follows. t u

We next prove Proposition 10, which is in some sense the obverse of the preceding one. Here x is already ahead of all other non-referenced elements; we move the non-referenced elements forward to their ending positions.

Proposition 10. As above, let S 0 be derived from the state S as follows:{ All referenced elements are in the same locations and in the same order in S 0 as in S .{ x occupies in S 0 the position of the front-most non-referenced element in S .{ All other non-referenced elements are in the same pairwise order in S 0 as in^ As above, let S be derived from the state S by moving x forward to immediately in front of the front-most non-referenced element. Then the cost x(S 0 ) of the^^ reference to x in state S 0, plus the distance d(S 0; S ) from S 0 to S, is less than the depth x(S ) of x in S by at least the number of non-referenced elements in front of x in S . That is, we have^ x(S 0 )+ d(S 0; S )+ jNj x(S ):Proof. Suppose x occupies the i0th non-referenced location from the front in S . (That is, jNj= i.) Denote the rst i non-referenced elements of S in order by q1;:::; qi= x. In S 0, the element qi?1 occupies position i; qi?2, position i? 1; and so on; q1 occupies position 2; and x occupies position 1. We transform^ S 0 to S by interchanging, for all 1< j< i, qj with all ref

erenced elements 10 In what follows, by slight abuse of notation, we refer to the location of the i th non-referenced element in T by the description\location i" or\position i".0

S.