Caching is hard - even in the fault model

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

doi:10.1007/s00453-011-9502-9

Caching is hard - even in the fault model

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

Research output: Contribution to journal › Article › Academic › peer-review

23 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 language	English
Pages (from-to)	781-794
Journal	Algorithmica
Volume	63
Issue number	4
DOIs	https://doi.org/10.1007/s00453-011-9502-9
Publication status	Published - 2012

Access to Document

10.1007/s00453-011-9502-9

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

Cite this

@article{f5c04db95ad64c43a8532f18e7a15d0e,

title = "Caching is hard - even in the fault model",

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.",

author = "M. Chrobak and G.J. Woeginger and K. Makino and Haifeng Xu",

year = "2012",

doi = "10.1007/s00453-011-9502-9",

language = "English",

volume = "63",

pages = "781--794",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer",

number = "4",

}

TY - JOUR

T1 - Caching is hard - even in the fault model

AU - Chrobak, M.

AU - Woeginger, G.J.

AU - Makino, K.

AU - Xu, Haifeng

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

U2 - 10.1007/s00453-011-9502-9

DO - 10.1007/s00453-011-9502-9

M3 - Article

VL - 63

SP - 781

EP - 794

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 4

ER -