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 ?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 max{2-p, 1+p(2-p)}, for any real number p ? [0,1]. Setting p = (3-?5)/2, we obtain a phi-competitive algorithm, where phi = (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.

ICSI Technical Report TR-94-071

Technical Report