Elsevier, Information Processing Letters, 2(116), p. 168-170, 2016
DOI: 10.1016/j.ipl.2015.09.004
Full text: Download
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 and Vogler. We provide a simpler proof based on a novel invariant condition maintained through an incremental procedure.