|
|||||||
|
|
|
|
|
|
|
||
| Report ID: | 06-04-12 |
| Initial Submission Date: | 2006-04-20 |
| Title: | A Short Proof of Optimality for the MIN Cache Replacement Algorithm |
| Summary: | The MIN algorithm is an offline strategy for deciding which item to replace when writing a new item to a cache. Its optimality has been established by Mattson, Gecsei, Slutz, and Traiger [2] through a lengthy analysis. We offer here a short and elementary proof based on a dynamic programming argument. |
| Authors: | Van Roy, Benjamin |
| Contact email: | bvr@stanford.edu |
| Number of views : 1019 Number of downloads : 753 |
| Version | Date | Accessible? | Download |
| 1 | 2006-04-20 | y | download |
| 2 | 2007-02-09 | y | download |