Randomized competitive algorithms for generalized caching

ABSTRACT

We consider online algorithms for the generalized caching problem. Here we are given a cache of size k and pages with arbitrary sizes and fetching costs. Given a request sequence of pages, the goal is to minimize the total cost of fetching the pages into the cache. We give an online algorithm with competitive ratio O(log²k), which is the first algorithm for the problem with competitive ratio sublinear in k. We also give improved O(log k)-competitive algorithms for the special cases of the Bit Model and Fault model. In the Bit Model, the fetching cost is proportional to the size of the page and in the Fault model all fetching costs are uniform. Previously, an O(log² k)-competitive algorithm due to Irani [14] was known for both of these models. Our algorithms are based on an extension of the primal-dual framework for online algorithms which was developed by Buchbinder and Naor [7]. We first generate an O(log k)-competitive fractional algorithm for the problem. This is done by using a strengthened LP formulation with knapsack-cover constraints, where exponentially many constraints are added upon arrival of a new request. Second, we round online the fractional solution and obtain a randomized online algorithm. Our techniques provide a unified framework for caching algorithms and are substantially simpler than those previously used.

REFERENCES

• 1: Dimitris Achlioptas , Marek Chrobak , John Noga, Competitive analysis of randomized paging algorithms, Theoretical Computer Science, v.234 n.1-2, p.203-218, March 6, 2000 [doi>10.1016/S0304-3975(98)00116-9]
• 2: Susanne Albers , Sanjeev Arora , Sanjeev Khanna, Page replacement for general caching problems, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.31-40, January 17-19, 1999, Baltimore, Maryland, United States
• 3: Nikhil Bansal , Niv Buchbinder , Joseph (Seffi) Naor, A Primal-Dual Randomized Algorithm for Weighted Paging, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.507-517, October 21-23, 2007 [doi>10.1109/FOCS.2007.7]
• 4: Amotz Bar-Noy , Reuven Bar-Yehuda , Ari Freund , Joseph (Seffi) Naor , Baruch Schieber, A unified approach to approximating resource allocation and scheduling, Journal of the ACM (JACM), v.48 n.5, p.1069-1090, September 2001 [doi>10.1145/502102.502107]
• 5: Reuven Bar-Yehuda , Dror Rawitz, On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique, SIAM Journal on Discrete Mathematics, v.19 n.3, p.762-797, 2005 [doi>10.1137/050625382]
• 6: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 7: N. Buchbinder and J. Naor. Online primal-dual algorithms for covering and packing problems. In Proceedings of the 13th Annual European Symposium on Algorithms, pages 689--701, 2005.
• 8: Pei Cao , Sandy Irani, Cost-aware WWW proxy caching algorithms, Proceedings of the USENIX Symposium on Internet Technologies and Systems on USENIX Symposium on Internet Technologies and Systems, p.18-18, December 08-11, 1997, Monterey, California
• 9: Robert D. Carr , Lisa K. Fleischer , Vitus J. Leung , Cynthia A. Phillips, Strengthening integrality gaps for capacitated network design and covering problems, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.106-115, January 09-11, 2000, San Francisco, California, United States
• 10: M. Chrobak , H. Karloff , T. Payne , S. Vishwanathan, New results on server problems, SIAM Journal on Discrete Mathematics, v.4 n.2, p.172-181, May 1991 [doi>10.1137/0404017]
• 11: Edith Cohen , Haim Kaplan, LP-based analysis of greedy-dual-size, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.879-880, January 17-19, 1999, Baltimore, Maryland, United States
• 12: Amos Fiat , Richard M. Karp , Michael Luby , Lyle A. McGeoch , Daniel D. Sleator , Neal E. Young, Competitive paging algorithms, Journal of Algorithms, v.12 n.4, p.685-699, Dec. 1991 [doi>10.1016/0196-6774(91)90041-V]
• 13: Sandy Irani, Competitive Analysis of Paging, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.52-73, January 1998
• 14: Sandy Irani, Page replacement with multi-size pages and applications to Web caching, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.701-710, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258666]
• 15: S. Irani. Randomized weighted caching with two page weights. Algorithmica, 32(4):624--640, 2002.
• 16: L. A. McGeoch and D. D. Sleator. A strongly competitive randomized paging algorithm. Algorithmica, 6(6):816--825, 1991.
• 17: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 18: Neal Young, On-line caching as cache size varies, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.241-250, January 28-30, 1991, San Francisco, California, United States
• 19: N. E. Young. The k-server dual and loose competitiveness for paging. Algorithmica, 11(6):525--541, 1994.
• 20: Neal E. Young, On-line file caching, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.82-86, January 25-27, 1998, San Francisco, California, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms

Keywords:
arbitrary sizes, arbitrary weights, caching, knapsack cover inequalities, online algorithms, primal-dual analysis