Finely-Competitive Paging

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.