A. Fiat, R. M. Karp, M. Luby, L. A. McGeoch, D. D. Sleator, N. E. Young, Competitive Paging Algorithms, Journal of Algorithms 12, 685-699 (1991)

Thepaging problemis that of deciding which pages to keep in a memory ofkpages in order to minimize the number of page faults. We develop themarking 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 2Hkof optimum.

(WhereHkis thekth harmonic number, which is roughly Ink.) The best such factor that can be achieved isHk. This is in contrast to deterministic algorithms, which cannot be guaranteed to be within a factor smaller thankof 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.

Daniel Sleator: Email, Home Page, Papers

Last modified: Sat Jan 21 07:15:44 EST 2006