A Proof of the Optimality of the MIN Paging Algorithm Using Linear Programming Duality

A linear programming formulation of the page replacement problem is used for proving the optimality of the MIN algorithm in a novel way. We describe an algorithm for constructing a solution for the dual problem such that the cost of this solution equals the cost of the MIN solution for the primal problem, thus proving the optimality of the MIN solution for paging, and the optimality of our algorithm for the paging dual (which is a special case of the assignment dual). Keywords: Analysis of algorithms; Paging; Linear programming; Duality; Assignment problem 1 Introduction The paging problem is the problem of managing hierarchical memory systems in which data is stored in units of equal size called pages. There is a fast memory which can hold a fixed number m of pages, and a slow memory which can hold all pages. Each of the m slots in the fast memory is called a frame. We are given a sequence of requests for pages (a reference string). In response to each request, the requested page m..