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 | |
Publication status | Published - 2012 |