A LOWER-BOUND FOR RANDOMIZED LIST UPDATE ALGORITHMS

There has been considerable effort to prove lower bounds for the competitiveness of a randomized list update algorithm. Lower bounds of 1.18 and (by a numerical technique) 1.27 were so far the best result. In this paper we construct a randomized request sequence sigma that no deterministic on-line algorithm can service with an expected cost less than 3/2-5/(n + 5) times the off-line cost (n denoting the length of the list). Using a result of Yao this establishes a new lower bound of 1.5 for the competitiveness of randomized list update algorithms.