Improved randomized on-line algorithms for the list update problem

The best randomized on-line algorithms known so far for the list update problem achieve a competitiveness of p 3 1:73. In this paper we present a new family of randomized on-line algorithms that beat this competitive ratio. Our improved algorithms are called TIMESTAMP algorithms and achieve a competitiveness of maxf2 p; 1 + p(2 p)g, for any real number p 2 [0; 1]. Setting p = (