Avrim Blum, Carl Burch, and Adam Kalai

extended abstract (FOCS '99, © 1999, by IEEE)

We construct an online algorithm for paging that achieves an
`O`(`r` + log `k`) competitive ratio
when compared to an offline strategy that
is allowed the additional ability to ``rent'' pages at a cost of
1/`r`. In contrast, the competitive ratio of the Marking algorithm
for this scenario is `O`(`r` log `k`).
Our algorithm can be thought of
in the standard setting as having a ``fine-grained''
competitive ratio, achieving an `O`(1) ratio when the request
sequence consists of a small number of working sets, gracefully
decaying to `O`(log `k`) as this number increases.

Our result is a generalization of the result in Bartal et al
[BBBT97] that one can achieve an `O`(`r` + log
`n`) ratio for the unfair `n`-state uniform-space
Metrical Task System problem. That result was a key component
of the polylog(`n`) competitive randomized algorithm
given in that paper for the general Metrical Task System problem.
One motivation of this work is that it may be a first step toward
achieving a polylog(`k`) randomized competitive ratio for
the much more difficult `k`-server problem.

Finely-competitive paging / Publications / Carl Burch