On List Update and Work Function Algorithms(13)

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

13

!t+1 (s0 ) !t (s0 )+ x(s0 ) !t (f )+ d(f; s0 )+ x(s0 ) !t (f )+ d(f; s)+ d(s; s0 )+ x(s0 )= !t (f )+ d(f; s)+ x(s), so !t+1 (s0 ) !t+1 (s). Since d(s0; st ) d(s0; s)+ d(s; st ), we also have !t+1 (s0 )+ (s0 )+ d(s0; st ) !t+1 (s)+ (s)+ d(s; st ). This means that s0 is wfa-eligible. And if the inequality !t+1 (s0 ) !t+1 (s). were strict, s could not be wfa-eligible; so we have speci cally !t+1 (s0 )= !t+1 (s). t uRecall from Proposition 6 that (s) (st ), so the work function algorithm cannot move x backward. We can now show that (a) there always exists a wfa-eligible state that requires no paid exchanges, and (b) that if WFA0 is restricted to moving the referenced element only, it is equivalent to the following algorithm (\Move-To-Min-!"):

Mtm!: On a reference to x, move x forward (or not at all) to a state with lowest work function value immediately after the reference.In other words, if st is the state the algorithm is in immediately before servicing the t+ 1-st request t+1, then Mtm! moves to a state st+1 such that st+1= argmins: s" s !t+1 (s) and satis es t+1 there. Summarizing:t x

cial case of Mtm!.

Proposition 8. Mtm! is a special case of WFA0 and Move-To-Front is a spe-

Proof. We rst show that Mtm! is a special case of WFA0 . That is, we need to show that a

ny state produced by Mtm! is wfa-eligible. Suppose s is such a state for which st" s, and s minimizes !t+1 (s) among all such. Let s0 be some wfaeligible state for which st" s0 . (The existence of such a state is demonstrated below.) Then either s0" s or s" s0 . If the former, Proposition 7 applies and s is wfa-eligible. If the latter, d(s; s0 )= (x(s)? x(s0 )) and !t+1 (s) !t+1 (s0 ) together imply that !t+1 (s)+ x(s)+ d(st; s) !t+1 (s0 )+ x(s0 )+ d(st; s0 ), and again s is wfa-eligible. It remains to demonstrate that there is at least one wfa-eligible state s for which st" s. For convenience in what follows, we denote generally by s the state^ formed from s by moving x to the front without changing the order of other elements, s"x s and x(^)= 1. We show that the move-to-front state st, the^ s^ state which simultaneously satis es st" st and x(st )= 1, is wfa-eligible. By^^ Proposition 7, there must be some r wfa-eligible for which x(r)= 1 (for any^ wfa-eligible r0, take r0 ). It is a basic fact of permutation distance that d(r; st )= d(r; st )+ d(st; st ), because the interchanges in d(r; st ) not involving x can all be^^ resolved rst, without moving x. Given this fact, then !t+1 (r)+ x(r)+ d(r; st )= !t+1 (r)+ x(st )+ d(r; st )+ d(st; st ). But !t+1 (r)+ d(r; st ) !t+1 (st ) by Propo^^^^^ sition 1, hence !t+1 (st )+ x(st )+ d(st; st ) !t+1 (r)+ x(r)+ d(st; r), which was^^^ to be proved. As a corollary, the move-to-front algorithm Move-To-Front is a special case of the work function algorithm. t u