Caching Is Hard–Even in the Fault Model

0.00 Avg rating—0 Votes

Article ID:	iaor20123973
Volume:	63
Issue:	4
Start Page Number:	781
End Page Number:	794
Publication Date:	Aug 2012
Journal:	Algorithmica
Authors:	Woeginger Gerhard, Chrobak Marek, Makino Kazuhisa, Xu Haifeng
Keywords:	computers: information

Abstract:

We prove strong $ℕℙ$ equ1 ‐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.

Reviews

Required fields are marked *. Your email address will not be published.