@inproceedings{1999finely,
author = {	, Avrim Blum and Burch, Carl and Kalai, Adam Tauman},
title = {Finely Competitive Paging},
booktitle = {FOCS '99 Proceedings of the 40th Annual Symposium on Foundations of Computer Science},
year = {1999},
month = {October},
abstract = {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.},
publisher = {IEEE},
url = {http://approjects.co.za/?big=en-us/research/publication/finely-competitive-paging/},
pages = {450-458},
isbn = {0-7695-0409-4},
edition = {FOCS '99 Proceedings of the 40th Annual Symposium on Foundations of Computer Science},
}