A short proof of optimality for the MIN cache replacement algorithm

DOI10.1016/J.IPL.2006.11.009zbMATHOpenAlexMaRDI QIDQ845965FDO

Authors Benjamin Van Roy

Publication date 29 January 2010

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

Full work available at URL https://doi.org/10.1016/j.ipl.2006.11.009

zbMATH Keywords

analysis of algorithmson-line algorithmspagingcaching

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Dynamic programming (90C39) Theory of software (68N99)

Recommendations

• Another short proof of optimality for the MIN cache replacement algorithm
• A simple proof of optimality for the MIN cache replacement policy
• A proof of the optimality of the MIN paging algorithm using linear programming duality
• scientific article; zbMATH DE number 1445384
• Towards a theory of cache-efficient algorithms
• On the complexity of cache analysis for different replacement policies
• Near optimality of the discrete persistent access caching algorithm
• An optimality proof of the LRU- K page replacement algorithm
• An \(O(\log k)\)-competitive algorithm for generalized caching
• An \(O(\log k)\)-competitive algorithm for generalized caching

Cited in

(6)

• A simple proof of optimality for the MIN cache replacement policy
• A proof of the optimality of the MIN paging algorithm using linear programming duality
• Another short proof of optimality for the MIN cache replacement algorithm
• Finding optimal non-datapath caching strategies via network flow
• Flexible resource allocation to interval jobs
• An optimality proof of the LRU- K page replacement algorithm

This page was built for publication: A short proof of optimality for the MIN cache replacement algorithm

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