On List Update and Work Function Algorithms(18)

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

186. N. Reingold and J. Westbrook. O -line algorithms for the list update problem. Information Processing Letters, 60(2):75{80, 1996. 7. S. Irani. Two results on the list update problem. Information Processing Letters, 38(6):301{306, 1991. 8. A. Borodin, N. Linial, and M. Saks. An optimal online algorithm for metrical task systems. Journal of the ACM, 52:46{52, 1985. 9. S. Roura and C. Martinez. On the competitiveness of the Move-to-front rule. Technical Report LSI-96-63-R, Technical University of Catalonia, 1997. 10. M. Chrobak and J. Noga. Competitive algorithms for multilevel caching and relaxed list update. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms, 1998. 11. F. Schulz. Two new families of list update algorithms. In Proceedings of 9th International Symposium, ISAAC, Vol. 1533 of Lecture Notes in Computer Science, pp. 99{ 108, 1998. 12. E. Koutsoupias and C. Papadimitriou. On the k-server conjecture. Journal of the ACM, 42(5): 971{983, September 1995. 13. M. Manasse, L. McGeoch and D.D. Sleator. Competitive algorithms for server problems. Journal of Algorithms, 11:208{230, 1990. 14. W. Burley and S. Irani. On algorithm design for metrical task systems. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms, 1995. 15. D.D. Sleator and R.E. Tarjan. Self-adjusting binary search trees. Journal of the ACM, 32: 652-686, 1985. 16. M. Chrobak, L. Larmore. The server problem and on-line games. In On-Line Algorithms, Proceedings of a DIMACS Workshop, Vol. 7 of DIMACS Series in Discrete Mathematics and Computer Science, pp. 11{ 64, 1991. 17. W.R. Burley. Traversing layered graphs using the work function algorithm. Journal of Algorithms, 20(3):479{511, 1996. 18. B. Teia. A lower bound for randomized list update algorithms. Information Processing Letters, 47:5{9, 1993. 19. S. Albers, B. von Stengel and R. Werchner. A combined BIT and TIMESTAMP algorithm for the list update problem. Information Processing Letters; 56: 135{ 139, 1995. 20. S. Albers. Private communication.

6 AppendixIn this Appendix, we address the proofs of the three propositions leading to Lemma 2. The most intricate part of the part of the construction is contained in Proposition 11; we save its proof for last.

Proposition 9. Suppose T 0 is derived from T, such that (i) all referenced ele-

ments p have p(T 0 )= p(T ), (ii) x occupies in T 0 the location of the front-most non-referenced element in T, and (iii) T 0 has the non-decreasing depth property, p(T 0) p(T ) for all p 6= x. Then the number of exchanges required to transform T to T 0 is bounded by (i) the number of interchanges involving x, plus (ii) the number of referenced elements, plus (iii) the number of interchanges involving non-refer

enced elements. In particular, the cost of the reference to x in T is equal to the cost of the reference in T 0, plus the number of interchanges involving x.