@article{bd6466c88bb640ce9ccfd430069ca76a,
title = "A simple proof of optimality for the MIN cache replacement policy",
abstract = "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.",
keywords = "Analysis of algorithms, Caching, MIN algorithm, Paging",
author = "Lee, {Mun Kyu} and Pierre Michaud and Sim, {Jeong Seop} and Nyang, {Dae Hun}",
note = "Funding Information: This work was supported in part by MSIP , Korea, under the ITRC support program (grant number: IITP-2015-H8501-15-1008 ) supervised by the IITP, in part by the National Research Foundation of Korea (NRF) grant funded by MSIP, Korea (grant number: 2014R1A2A1A11050337 ), and in part by Inha University Research Grant. Publisher Copyright: {\textcopyright} 2015 Elsevier B.V.",
year = "2016",
month = feb,
doi = "10.1016/j.ipl.2015.09.004",
language = "English",
volume = "116",
pages = "168--170",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier",
number = "2",
}