| Article ID: | iaor201530342 |
| Volume: | 116 |
| Issue: | 2 |
| Start Page Number: | 168 |
| End Page Number: | 170 |
| Publication Date: | Feb 2016 |
| Journal: | Information Processing Letters |
| Authors: | Lee Mun-Kyu, Michaud Pierre, Sim Jeong Seop, Nyang DaeHun |
| Keywords: | decision, statistics: sampling, datamining |
The MIN cache replacement algorithm is an optimal off-line policy to decide which item to evict when a new item should be fetched into a cache. Recently, two short proofs were given by van Roy (2007) [3] and Vogler (2008) [4]. We provide a simpler proof based on a novel invariant condition maintained through an incremental procedure.