On List Update and Work Function Algorithms(12)

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

12 El-Yaniv shows that MRI (1) is equivalent (except for the rst move of each element) to TimeStamp. Because any element that is requested more than twice since the last reference to x must be incomparable to x after the reference to x, the result follows for all k. Schulz has recently presented the SBR( ) family 11]. From his Lemma 1 and the de nition, the referenced element is moved forward at least as far as TimeStamp. As shown above, any such algorithm maintains a list order consistent with the partial order. We have shown:

Corollary 1. Move-To-Front, TimeStamp, RTS and SBR( ) are all (2?1=k)competitive.

4 On the performance of work function algorithms4.1 PreliminariesWe begin with some de nitions and fa

cts. In what follows, the (t+ 1)st request t+1 is x. The task cost (s) is denoted x(s), which is the depth of x in the list con guration s. As before, we denote by st the state visited by the work function algorithm at time t, immediately before servicing the request to x.8 We rst de ne the"x binary relation on two states.

s by moving x forward while leaving the relative positions of other elementsundisturbed.

De nition 6. s"x s0 i s and s0 are identical, or if s0 can be derived from

Where x is understood from context, we write simply s" s0 .

Proposition 7. Suppose s is wfa-eligible, and s"x s0. Then !t+1(s) !t+1(s0).

(Moving x forward cannot increase the work function.) Furthermore, s0 is wfaeligible, and !t+1 (s)= !t+1 (s0 ). Proof. In the case of list update, the\free exchange" cost model implies that whenever s"x s0, x(s)= x(s0 )+ d(s; s0 ). Suppose rst that s is fundamental, !t+1 (s)= !t (s)+ x(s). We have !t+1 (s0 ) !t (s0 )+ x(s0 ) by Proposition 3, and !t (s0 ) !t(s)+ d(s0; s) by Proposition 1, so !t+1 (s0 ) !t (s)+ d(s0; s)+ x(s0 ). But d(s0; s)+ x(s0 )= x(s) so !t+1(s0 ) !t(s)+ x(s)= !t+1 (s) as was to be shown. Next suppose that s is wfa-eligible. By Proposition 1, we have !t+1 (s)= !t+1 (f )+ d(f; s) for some fundamental state f, for which also x(f )= x(s). This means that !t+1 (s)= !t (f )+ d(f; s)+ x(f )= !t (f )+ d(f; s)+ x(s): But 8 Again, we do not distinguish between a reference to x followed by free exchanges, on the one hand, and\paid" exchanges moving x forward, followed by a lower-cost reference to x, on the other. We refer to either of these combined steps as\servicing" the request to x.