COUNTER algorithms, a family of randomized algorithms for the list update problem, were introduced by Reingold, Westbrook and Sleator. 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.
Appears in Information Processing Letters, vol. 64, pp. 155-160, 1997. Copyright by them, all rights reserved by them, follow their copyright procedure, etc.