Caching is hard - even in the fault model

M. Chrobak, G.J. Woeginger, K. Makino, Haifeng Xu

Research output: Contribution to journalArticleAcademicpeer-review

33 Citations (Scopus)


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 languageEnglish
Pages (from-to)781-794
Issue number4
Publication statusPublished - 2012


Dive into the research topics of 'Caching is hard - even in the fault model'. Together they form a unique fingerprint.

Cite this