Caching is hard -- even in the fault model

DOI10.1007/s00453-011-9502-9zbMath1364.68218OpenAlexW2053460412MaRDI QIDQ692624

Kazuhisa Makino, Marek Chrobak, Gerhard J. Woeginger, Hai-Feng Xu

Publication date: 6 December 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9502-9

zbMATH Keywords

hardnesspagingpage replacementcaching problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Theory of operating systems (68N25)

Related Items (7)

Flexible bandwidth assignment with application to optical networks ⋮ General caching is hard: even with small pages ⋮ Approximations for generalized unsplittable flow on paths with application to power systems optimization ⋮ On improved interval cover mechanisms for crowdsourcing markets ⋮ A constant factor approximation algorithm for the storage allocation problem ⋮ Flexible resource allocation to interval jobs ⋮ Online file caching with rejection penalties

Cites Work

• On-line file caching
• Page replacement with multi-size pages and applications to web caching
• A quasi-PTAS for unsplittable flow on line graphs
• New Ressults on Server Problems
• A logarithmic approximation for unsplittable flow on line graphs
• A unified approach to approximating resource allocation and scheduling
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Caching is hard -- even in the fault model