General Caching Is Hard: Even with Small Pages
Authors:
Preprint
Abstract
Caching (also known as paging) is a classical problem concerning page replacement policies in two-level memory systems. General caching is the variant with pages of different sizes and fault costs. We give the first NP-hardness result for general caching with small pages: General caching is (strongly) NP-hard even when page sizes are limited to {1, 2, 3}. It holds already in the fault model (each page has unit fault cost) as well as in the bit model (each page has the same fault cost as size). We also give a very short proof of the strong NP-hardness of general caching with page sizes restricted to {1, 2, 3} and arbitrary costs.Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- A logarithmic approximation for unsplittable flow on line graphsACM Transactions on Algorithms, 2014
- Caching Is Hard—Even in the Fault ModelAlgorithmica, 2011
- Page Replacement with Multi-Size Pages and Applications to Web CachingAlgorithmica, 2002
- On-Line File CachingAlgorithmica, 2002
- A unified approach to approximating resource allocation and schedulingJournal of the ACM, 2001
- New Ressults on Server ProblemsSIAM Journal on Discrete Mathematics, 1991
- A study of replacement algorithms for a virtual-storage computerIBM Systems Journal, 1966