Abstract
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 (uniform 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. This paper seeks to develop good of online 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 additional memory is allowed, one can obtain an O(log(M+C))-approximation where and C denote the cache size and the largest page fault cost, respectively. Our results use a new rounding technique for linear programs which may be of independent interest. We also present a randomized online algorithm for the Bit Model which achieves a competitive ratio of O(ln(1+1/c)) while using M(1+c) memory.
Original language | English (US) |
---|---|
Pages | 31-40 |
Number of pages | 10 |
State | Published - 1999 |
Externally published | Yes |
Event | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA Duration: Jan 17 1999 → Jan 19 1999 |
Other
Other | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|
City | Baltimore, MD, USA |
Period | 1/17/99 → 1/19/99 |
All Science Journal Classification (ASJC) codes
- Software
- General Mathematics