| Competitive Paging Algorithms Amos Fiat 1 (2007) | |||||||||||||||
Abstract | |||||||||||||||
| The paging problem is that of deciding which pages to keep in a memory of k pages in order to minimize the number of page faults. We develop the marking algorithm, a randomized on-line algorithm for the paging problem. We prove that its expected cost on any sequence of requests is within a factor of 2H k of optimum. (Where H k is the kth harmonic number, which is roughly ln k.) The best such factor that can be achieved is H k. This is in contrast to deterministic algorithms, which cannot be guaranteed to be within a factor smaller than k of optimum. An alternative to comparing an on-line algorithm with the optimum offline algorithm is the idea of comparing it to several other on-line algorithms. We have obtained results along these lines for the paging problem. Given a set of on-line algorithms and a set of appropriate constants, we describe a way of constructing another on-line algorithm whose performance is within the appropriate constant factor of each algorithm in the set. | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||