Randomized competitive algorithms for generalized caching

N. Bansal, N. Buchbinder, J. Naor

Research output: Contribution to journalArticleAcademicpeer-review

18 Citations (Scopus)
117 Downloads (Pure)

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. Our main result is an online algorithm with competitive ratio $O(\log^2k)$, which gives the first $o(k)$ competitive algorithm for the problem. We also give improved $O(\log k)$-competitive algorithms for the special cases of the bit model and fault model, improving upon the previous $O(\log^2k)$ guarantees due to Irani [Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, pp. 701–710]. Our algorithms are based on an extension of the online primal-dual framework introduced by Buchbinder and Naor [Math. Oper. Res., 34 (2009), pp. 270–286] and involve two steps. First, we obtain an $O(\log k)$-competitive fractional algorithm based on solving online an LP formulation strengthened with exponentially many knapsack cover constraints. Second, we design a suitable online rounding procedure to convert this online fractional algorithm into a randomized algorithm. Our techniques provide a unified framework for caching algorithms and are substantially simpler than those previously used.
Original languageEnglish
Pages (from-to)391-414
JournalSIAM Journal on Computing
Volume41
Issue number2
DOIs
Publication statusPublished - 2012

Fingerprint

Dive into the research topics of 'Randomized competitive algorithms for generalized caching'. Together they form a unique fingerprint.

Cite this