## Competitive paging algorithms

- Author(s): Fiat, A
- Karp, RM
- Luby, M
- McGeoch, LA
- Sleator, DD
- Young, NE
- et al.

## 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 of optimum. (Where H is the kth harmonic number, which is roughly ln k.) The best such factor that can be achieved is H . 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 off-line 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. © 1991. k k k

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.