On List Update and Work Function Algorithms(17)

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

17 less than x immediately before its nal reference that were incomparable to x immediately before the penultimate reference to x. We have r1+r2 G+I+L(0). Denote by t1 the time of the penultimate reference to x, and by t2 the time of the nal reference. Since each element in L(0) at time t2 is incomparable to x at time t1, we have L(0)P It1 . That is, for any t2, there is some t1< t2 such t2 P P P that L(0)t2 It1 . Thus t L(0)t t Gt by the counting t It . But t It argument, Lemma 1. Summarizing, we have

WFA0 ( )2X

X

Therefore, Mtm! is at least 6-competitive. t u Note that, for list update, the algorithm WFA (without the subscript) can be less e ective than WFA0 . Consider the sequence= bbb for a two-element list (a; b). After the second reference to b, the list con guration (b; a) has strictly lower work function value. But WFA does not (necessarily) move to that state until after the third reference to b. However, as noted above it is possible (by expanding the construction of the DFA to more states) to extend the above proof of O(1)-competitiveness to WFA. It is fairly clear that the competitive ratios shown by our analyses of these algorithms are not tight. The above example shows that WFA, even without paid exchanges, is no better than 3-competitive.

t

(Gt+ It+ L(0)t ) 6

t

(2r1+ r2 ) 2(r1+ r2 )X

t

Gt 6OPT ( )

5 AcknowledgmentsWe gratefully acknowledge discussions with Susanne Albers, Ran El-Yaniv, Sandy Irani, and T.S. Jayram. This work was supported in part by NSF grant EIA-9870740 and BSF grant 96-00247 (Karlin), the CRA Distributed Mentor Project (Hildrum and Rasala), and an IBM Research Fellowship (Anderson).

References1. S. Albers and J. Westbrook. Self-organizing data structures. In Online Algorithms: The State of the Art, Fiat-Woeginger, Springer, 1998. 2. D.D. Sleator and R.E. Tarjan. Amortized e ciency of list update and paging rules. Communications of the ACM, 28:202{208, 1985. 3. J.L. Bentley and C. McGeoch. Amortized analysis of self-organizing sequential search heuristics. Communications of the ACM, 28(4):404{411, 1985. 4. S. Albers. Improved randomized on-line algorithms for the

list update problem. SIAM Journal on Computing, 27: 682{693, 1998. 5. R. El-Yaniv. There are in nitely many competitive-optimal online list accessing algorithms. Discussion paper from The Center for Rationality and Interactive Decision Making. Hebrew University.