Department of Computer Science | Institute of Theoretical Computer Science

The list update problem is a classical online problem, with an optimal
competitive ratio that is still open, known to be somewhere between
1.5 and 1.6. An algorithm with competitive ratio 1.6, the smallest
known to date, is COMB, a randomized combination of BIT and the
TIMESTAMP algorithm TS. This and almost all other list update
algorithms, like MTF, are projective in the sense that they can be
defined by looking only at any pair of list items at a
time. Projectivity (also known as âlist factoringâ) simplifies both
the description of the algorithm and its analysis, and so far seems to
be the only way to define a good online algorithm for lists of
arbitrary length. In this article, we characterize all projective list
update algorithms and show that their competitive ratio is never
smaller than 1.6 in the partial cost model. Therefore, COMB is a best
possible projective algorithm in this model.