A short proof of optimality for the MIN cache replacement algorithm

DOI10.1016/J.IPL.2006.11.009zbMATH Open1184.68192OpenAlexW1963831729MaRDI QIDQ845965FDOQ845965

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

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

zbMATH Keywords

analysis of algorithmson-line algorithmspagingcaching

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (6)

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

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)