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