Abstract
We prove strong \({\mathbb {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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Albers, S., Arora, S., Khanna, S.: Page replacement for general caching problems. In: Proc. 10th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA’99), pp. 31–40 (1999)
Bansal, N., Chakrabarti, A., Epstein, A., Schieber, B.: A quasi-PTAS for unsplittable flow on line graphs. In: Proc. 38th Annual ACM Symposium on Theory of Computing (STOC’06), pp. 721–729 (2006)
Bansal, N., Buchbinder, N., Naor, J.: Randomized competitive algorithms for generalized caching. In: Proc. 40th Annual ACM Symposium on Theory of Computing (STOC’08), pp. 235–244 (2008)
Bansal, N., Friggstad, Z., Khandekar, R., Salavatipour, M.R.: A logarithmic approximation for unsplittable flow on line graphs. In: Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’09), pp. 702–709 (2009)
Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., Schieber, B.: A unified approach to approximating resource allocation and scheduling. J. ACM 48, 1069–1090 (2000)
Belady, L.A.: A study of replacement algorithms for virtual-storage computer. IBM Syst. J. 5, 78–101 (1966)
Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)
Brehob, M., Wagner, S., Torng, E., Enbody, R.: Optimal replacement is NP-hard for non-standard caches. IEEE Trans. Comput. 53, 73–76 (2004)
Cao, P., Irani, S.: Cost-aware www proxy caching algorithms. In: Proc. USENIX Symposium on Internet Technologies and Systems, pp. 193–206 (1997)
Chrobak, M., Karloff, H.J., Payne, T.H., Vishwanathan, S.: New results on server problems. SIAM J. Discrete Math. 4, 172–181 (1991)
Fiat, A.: Unpublished manuscript, 1997
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of \({\mathbb {NP}}\)-Completeness. Freeman, San Francisco (1979)
Irani, S.: Page replacement with multi-size pages and applications to web caching. Algorithmica 33, 384–409 (1997)
Young, N.E.: On-line file caching. Algorithmica 33, 371–383 (2002)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Chrobak, M., Woeginger, G.J., Makino, K. et al. Caching Is Hard—Even in the Fault Model. Algorithmica 63, 781–794 (2012). https://doi.org/10.1007/s00453-011-9502-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-011-9502-9