2 RESULTS ON THE LIST UPDATE PROBLEM

In this paper we give a randomized on-line algorithm for the list update problem. Sleator and Tarjan show a deterministic algorithm, Move-to-Front, that achieves competitive ratio of (2L - 1)/L for lists of length L. Karp and Raghavan show that no deterministic algorithm can beat 2L/(L + 1). We show that Move-to-Front in fact achieves an optimal competitive ratio of 2L/(L + 1). We show a randomized algorithm that achieves a competitive ratio of (31L + 1)/16(L + 1) against an oblivious adversary. This is the first randomized strategy whose competitive factor beats a constant less than 2.