@inproceedings{74efbc05344a40c1a77e4d46b943bbe7,
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 = "2010",
doi = "10.1007/978-3-642-15775-2\_17",
language = "English",
isbn = "978-3-642-15774-5",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "195--206",
editor = "\{Berg, de\}, M. and U. Meyer",
booktitle = "Algorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I)",
address = "Germany",
}