DIMACS TR: 97-69

Uniform Multipaging Reduces to Paging

Author: Vincenzo Liberatore


Multipaging is the paging problem when more than one page can be requested at each step. In the uniform cost model, a paging algorithm is charged for the number of pages loaded from disk to fast memory. In this note, we establish a general reduction from uniform multipaging to paging. As a consequence, we obtain the first strongly competitive randomized algorithm for uniform multipaging.

DIMACS activities: Research supported by a Summer DIMACS Graduate Fellowship.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-69.ps.gz

DIMACS Home Page