On List Update and Work Function Algorithms(7)

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

7Proof. Since s is wfa-eligible, it minimizes the expression in De nition 4, !t+1 (s)+ (s)+ d(st; s) !t+1 (s0 )+ (s0 )+ d(st; s0 ) for all s0 . If we show that !t+1 (f )+ (f )+ d(st; f ) !t+1 (s)+ (s)+ d(st; s), then f minimizes that expression as well, and f then must also be wfa-eligible. We observe rst that (f ) (s). By Propositions 2 and 3, !t+1 (s) !t (s)+ (s) !t (f )+ (s)+ d(f; s). Then (s)< (f ) would imply !t+1 (s)< !t (f )+ (f )+ d(f; s)= !t+1 (f )+ d(f; s). By hypothesis, however, we have !t+1 (f )+ d(f; s)= !t+1 (s). Next, by the triangle inequality, d(st; f ) d(st; s)+ d(f; s). Then !t+1 (f )+ d(st; f ) !t+1 (f )+ d(st; s)+ d(f; s)= !t+1 (s)+ d(st; s). Since (f ) (s), we have !t+1 (f )+ d(st; f )+ (f ) !t+1 (s)+ d(st; s)+ (s), and f is wfa-eligible. Finally, since s is also wfa-eligible, the above inequality cannot be strict. It would be if (f )< (s), so we must have (f )= (s). t u

Proposition 6. If s is wfa-eligible, then (s)

(st ).

Proof. Suppose instead that (s)> (st ). Then the condition for s to be wfaeligible (De nition 4) is !t+1 (s)+ (s)+ d(s; st )> !t+1 (s)+ (st )+ d(s; st ) !t+1 (st )+ (st ) by Proposition 1. But this last expression is De nition 4 applied to the state st . If st satis es De nition 4 strictly more strongly than s, s cannot be wfa-eligible. t u

2.3 ObservationsThe work function algorithm can be viewed as a compromise between two very natural algorithms. First, a natural greedy algorithm tries to minimize the cost spent on the current step. It services the (t+ 1)st request in a state s that minimizes d(st; s)+ (s): Another natural algorithm is a retrospective algorithm, which tries to match the state chosen by the optimal o ine algorithm. It services the (t+ 1)st request in a state s that minimizes !t+1 (s). Each of these natural algorithms is known to be noncompetitive for many metrical task systems. WFA combines these approaches and, interestingly, this results in an algorithm which is known to be strongly competitive for a number of problems for which neither the greedy and retrospective algorithms are competitive.4 The di erence between WFA and the variant, WFA0, is in the subscript of the work function. We actually feel that WFA0 is a slightly more natural algorithm, in light of the discussion above about combining a greedy approach and a retrospective approach. It is this latter work function algorithm WFA0 that we will focus on in this paper. It is fairly easy to extend our proof that WFA0 is O(1) competitive for list update to handle WFA as well. 54 Varying the relative weighting

of the greedy and retrospective components of the 5 In addition, many prior results which hold for

work function algorithm was explored in 17].

WFA also hold for WFA . For example, for the k-server problem the work function values at t and t+ 1 are identical0