Caching is hard - even in the fault model

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

Research output: Contribution to journalArticleAcademicpeer-review

21 Citations (Scopus)

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

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

  • Cite this