Page Replacement for General Caching Problems

Caching (paging) is a well-studied problem in online algorithms, usually studied under the assumption that all pages have a uniform size and a uniform fault cost (uni- form caching). However, recent applications related to the web involve situations in which pages can be of different sizes and costs. This general caching problem seems more intricate than the uniform version. In particular, the offline case itself is NP-hard. Only a few results exist for the general caching problem [8, 17]. This paper seeks to develop good offline page replacement policies for the general caching problem, with the hope that any insight gained here may lead to good online algorithms. Our first main result is that by using only a small amount of additional memory, say O(1) times the largest page size, we can obtain an O(1)-approximation to the general caching problem. Note that the largest page size is typically a very small fraction of the total cache size, say 1%. Our second result is that when no add..