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 (1994). They showed that for any epsilon > 0, there exist COUNTER algorithms that achieve a competitive ratio of sqrt{3} + epsilon. In this paper we use a mixture of two COUNTER algorithms to achieve a competitiveness of 12/7, which is less than sqrt{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.