####
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.