Caching is hard, even in the fault model

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

20 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
Title of host publicationAlgorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I)
EditorsM. Berg, de, U. Meyer
Place of PublicationBerlin
ISBN (Print)978-3-642-15774-5
Publication statusPublished - 2010

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


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

Cite this