The List Update Problem: Improved Bounds for the Counter Scheme

Abstract.

We consider the problem of dynamic reorganization of a linear list, where requests for the elements are generated randomly with fixed, unknown probabilities. The objective is to obtain the smallest expected cost per access. It has been shown, that when no a priori information is given on the reference probabilities, the Counter Scheme (CS) provides an optimal reorganization rule, which applies to all possible distributions. In this paper we show that for a list of n elements, arbitrary request probabilities, and $\alpha$ >0 the expected cost under CS achieves a ratio of at most 1+ $\alpha$ to the optimal (minimal) expected cost within Qn lg n $\alpha$ ² reorganization steps, for a Q we can compute.