Revisiting the COUNTER Algorithms for List Update

COUNTER algorithms, a family of randomized algorithms for the list update problem, were introduced by Reingold, Westbrook, and Sleator [7]. They showed that for any ffl ? 0, there exist COUNTER algorithms that achieve a competitive ratio of p 3 + ffl. In this paper we use a mixture of two COUNTER algorithms to achieve a competitiveness of 12=7, which is less than p 3. Furthermore, we demonstrate that it is impossible to prove a competitive ratio smaller than 12=7 for any mixture of COUNTER algorithms using the type of potential function argument that has been used so far. We also provide new lower bounds for the competitiveness of COUNTER algorithms in the standard cost model, including a 1.625 lower bound for the variant BIT and a matching 12/7 lower bound for our algorithm. Keywords: List update; On-line algorithms; Randomized algorithms; Data structures. 1 Introduction The list update problem, a fundamental and extensively studied on-line problem, is to maintain an unsorted lin..