TY - GEN
T1 - Improved randomized on-line algorithms for the list update problem
AU - Albers, Susanne
N1 - Funding Information:
Berkeley, CA 94704; and Max Planck Institute for Computer Science, Saarbriicken, Germany. Supported in part by an Otto Hahn Medal Award of the Max Planck Society and by the ESPRIT Basic Research Actions Program of the EU under contract No. 7141 (project ALCOM II).
PY - 1995/1/22
Y1 - 1995/1/22
N2 - The best randomized on-line algorithms known so far for the list update problem achieve a competitiveness of √3 ≈ 1.73. In this paper we present a new family of randomized online algorithms that beat this competitive ratio. Our improved algorithms are called TIMESTAMP algorithms and achieve a competitiveness of max{2-p, 1+p(2-p)}, for any real number p ϵ [0, 1]. Setting p = (3 - √5)/2, we obtain a (φ-competitive algorithm, where φ = (1 + √5)/2 ≈ 1.62 is the Golden Ratio. TIMESTAMP algorithms coordinate the movements of items using some information on past requests. We can reduce the required information at the expense of increasing the competitive ratio. We present a very simple version of the TIMESTAMP algorithms that is 1.68-competitive. The family of TIMESTAMP algorithms also includes a new deterministic 2-competitive on-line algorithm that is different from the MOVE-TO-FRONT rule.
AB - The best randomized on-line algorithms known so far for the list update problem achieve a competitiveness of √3 ≈ 1.73. In this paper we present a new family of randomized online algorithms that beat this competitive ratio. Our improved algorithms are called TIMESTAMP algorithms and achieve a competitiveness of max{2-p, 1+p(2-p)}, for any real number p ϵ [0, 1]. Setting p = (3 - √5)/2, we obtain a (φ-competitive algorithm, where φ = (1 + √5)/2 ≈ 1.62 is the Golden Ratio. TIMESTAMP algorithms coordinate the movements of items using some information on past requests. We can reduce the required information at the expense of increasing the competitive ratio. We present a very simple version of the TIMESTAMP algorithms that is 1.68-competitive. The family of TIMESTAMP algorithms also includes a new deterministic 2-competitive on-line algorithm that is different from the MOVE-TO-FRONT rule.
UR - http://www.scopus.com/inward/record.url?scp=84948962002&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84948962002
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 412
EP - 419
BT - Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
PB - Association for Computing Machinery
T2 - 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
Y2 - 22 January 1995 through 24 January 1995
ER -