A simple proof of optimality for the MIN cache replacement policy

DOI10.1016/J.IPL.2015.09.004MaRDI QIDQ894469zbMATH OpenOpenAlexFDO

Authors Mun-Kyu Lee, Pierre Michaud, J. S. Sim, DaeHun Nyang

Publication date 1 December 2015

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-01199424/file/halversion.pdf

zbMATH Keywords

analysis of algorithmspagingcachingMIN algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Theory of operating systems (68N25)

Recommendations

• A short proof of optimality for the MIN cache replacement algorithm
• Another short proof of optimality for the MIN cache replacement algorithm
• A proof of the optimality of the MIN paging algorithm using linear programming duality
• An optimality proof of the LRU- K page replacement algorithm
• scientific article; zbMATH DE number 1305389

Cites work

• A short proof of optimality for the MIN cache replacement algorithm
• Another short proof of optimality for the MIN cache replacement algorithm

Cited in

(6)

• A proof of the optimality of the MIN paging algorithm using linear programming duality
• Optimal eviction policies for stochastic address traces
• Another short proof of optimality for the MIN cache replacement algorithm
• A short proof of optimality for the MIN cache replacement algorithm
• Minimizing I/Os in Out-of-Core Task Tree Scheduling
• An optimality proof of the LRU- K page replacement algorithm

This page was built for publication: A simple proof of optimality for the MIN cache replacement policy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q894469)