×

On list update and work function algorithms. (English) Zbl 1061.68056

Summary: 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 constant competitive ratio for list update. In the process, we present a new formulation of the well-known “list factoring” technique in terms of a partial order on the elements of the list. This approach leads to a new simple proof that a large class of online algorithms, including Move-To-Front, is \((2-1/k)\)-competitive, for \(k\) the list length.

MSC:

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68P05 Data structures
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albers, S., Improved randomized on-line algorithms for the list update problem, SIAM J. Comput., 27, 682-693 (1998) · Zbl 0907.68054
[2] S. Albers, Private communication.; S. Albers, Private communication.
[3] Albers, S.; von Stengel, B.; Werchner, R., A combined BIT and TIMESTAMP algorithm for the list update problem, Inform. Process. Lett., 56, 135-139 (1995) · Zbl 0875.68392
[4] S. Albers, J. Westbrook, Self-organizing data structures, in: Online Algorithms: The State of the Art, Fiat-Woeginger, Springer, Berlin, 1998.; S. Albers, J. Westbrook, Self-organizing data structures, in: Online Algorithms: The State of the Art, Fiat-Woeginger, Springer, Berlin, 1998.
[5] Bentley, J. L.; McGeoch, C., Amortized analysis of self-organizing sequential search heuristics, Commun. ACM, 28, 4, 404-411 (1985)
[6] Borodin, A.; Linial, N.; Saks, M., An optimal online algorithm for metrical task systems, J. ACM, 52, 46-52 (1995)
[7] Burley, W. R., Traversing layered graphs using the work function algorithm, J. Algorithms, 20, 3, 479-511 (1996) · Zbl 0845.68051
[8] W. Burley, S. Irani, On algorithm design for metrical task systems, ACM-SIAM Symp. on Discrete Algorithms, 1995.; W. Burley, S. Irani, On algorithm design for metrical task systems, ACM-SIAM Symp. on Discrete Algorithms, 1995. · Zbl 0853.68062
[9] M. Chrobak, L. Larmore, The server problem and on-line games, On-Line Algorithms, Proc. DIMACS Workshop, DIMACS Series in Discrete Mathematics and Computer Science, Vol. 7, 1991, pp. 11-64.; M. Chrobak, L. Larmore, The server problem and on-line games, On-Line Algorithms, Proc. DIMACS Workshop, DIMACS Series in Discrete Mathematics and Computer Science, Vol. 7, 1991, pp. 11-64. · Zbl 0800.68489
[10] M. Chrobak, J. Noga, Competitive algorithms for multilevel caching and relaxed list update, Proc. of ACM-SIAM Symp. on Discrete Algorithms, 1998.; M. Chrobak, J. Noga, Competitive algorithms for multilevel caching and relaxed list update, Proc. of ACM-SIAM Symp. on Discrete Algorithms, 1998. · Zbl 0936.68003
[11] R. El-Yaniv, There are infinitely many competitive-optimal online list accessing algorithms, Discussion paper from The Center for Rationality and Interactive Decision Making, Hebrew University.; R. El-Yaniv, There are infinitely many competitive-optimal online list accessing algorithms, Discussion paper from The Center for Rationality and Interactive Decision Making, Hebrew University.
[12] Irani, S., Two results on the list update problem, Inform. Process. Lett., 38, 6, 301-306 (1991) · Zbl 0737.68043
[13] Koutsoupias, E.; Papadimitriou, C., On the \(k\)-server conjecture, J. ACM, 42, 5, 971-983 (1995) · Zbl 0885.68075
[14] Manasse, M.; McGeoch, L.; Sleator, D. D., Competitive algorithms for server problems, J. Algorithms, 11, 208-230 (1990) · Zbl 0705.68023
[15] Reingold, N.; Westbrook, J., Off-line algorithms for the list update problem, Informat. Process. Lett., 60, 2, 75-80 (1996) · Zbl 0875.68546
[16] S. Roura, C. Martinez, On the competitiveness of the Move-to-front rule, Technical Report LSI-96-63-R, Technical University of Catalonia, 1997.; S. Roura, C. Martinez, On the competitiveness of the Move-to-front rule, Technical Report LSI-96-63-R, Technical University of Catalonia, 1997. · Zbl 0947.68166
[17] F. Schulz, Two new families of list update algorithms, Proc. Ninth Int. Symp., ISAAC, Lecture Notes in Computer Science, Vol. 1533, Springer, Berlin, 1998, pp. 99-108.; F. Schulz, Two new families of list update algorithms, Proc. Ninth Int. Symp., ISAAC, Lecture Notes in Computer Science, Vol. 1533, Springer, Berlin, 1998, pp. 99-108.
[18] Sleator, D. D.; Tarjan, R. E., Amortized efficiency of list update and paging rules, Commun. ACM, 28, 202-208 (1985)
[19] Sleatorm, D. D.; Tarjan, R. E., Self-adjusting binary search trees, J. ACM, 32, 652-686 (1985) · Zbl 0631.68060
[20] Teia, B., A lower bound for randomized list update algorithms, Inform. Process. Lett., 47, 5-9 (1993) · Zbl 0794.68070
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.