Caching Is Hard–Even in the Fault Model

Caching Is Hard–Even in the Fault Model

0.00 Avg rating0 Votes
Article ID: iaor20123973
Volume: 63
Issue: 4
Start Page Number: 781
End Page Number: 794
Publication Date: Aug 2012
Journal: Algorithmica
Authors: , , ,
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.