Abstract
We prove strong NP-completeness for the four variants of caching with multi-size pages. These four variants are obtained by choosing either the fault cost or the bit cost model, and by combining it with either a forced or an optional caching policy. This resolves two questions in the area of paging and caching that were open since the 1990s.
| Original language | English |
|---|---|
| Pages (from-to) | 781-794 |
| Journal | Algorithmica |
| Volume | 63 |
| Issue number | 4 |
| DOIs | |
| Publication status | Published - 2012 |
Fingerprint Dive into the research topics of 'Caching is hard - even in the fault model'. Together they form a unique fingerprint.
Cite this
Chrobak, M., Woeginger, G. J., Makino, K., & Xu, H. (2012). Caching is hard - even in the fault model. Algorithmica, 63(4), 781-794. https://doi.org/10.1007/s00453-011-9502-9