A proof of the optimality of the MIN paging algorithm using linear programming duality

A proof of the optimality of the MIN paging algorithm using linear programming duality

0.00 Avg rating0 Votes
Article ID: iaor19971087
Country: Netherlands
Volume: 18
Issue: 1
Start Page Number: 7
End Page Number: 13
Publication Date: Aug 1995
Journal: Operations Research Letters
Authors: ,
Keywords: duality
Abstract:

A linear programming formulation of the page replacement problem is used for proving the optimality of the MIN algorithm in a novel way. The authors 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).

Reviews

Required fields are marked *. Your email address will not be published.