{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:25:04Z","timestamp":1787340304076,"version":"build-2736575974"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>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\u2013710]. 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\u2013286] 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.<\/jats:p>","DOI":"10.1137\/090779000","type":"journal-article","created":{"date-parts":[[2012,4,20]],"date-time":"2012-04-20T08:42:59Z","timestamp":1334911379000},"page":"391-414","source":"Crossref","is-referenced-by-count":19,"title":["Randomized Competitive Algorithms for Generalized Caching"],"prefix":"10.1137","volume":"41","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Niv","family":"Buchbinder","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,4,19]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00116-9"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"A. Adamaszek, A. Czumaj, M. Englert, and H. R\u00e4cke,\n                      An $O(\\log k)$-competitive algorithm for generalized caching\n                      , in Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, Kyoto, Japan, 2012, pp. 1681\u20131689.","DOI":"10.1137\/1.9781611973099.133"},{"key":"R3","unstructured":"S. Albers, S. Arora, and S. Khanna,\n                      Page replacement for general caching problems\n                      , in Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, 1999, pp. 31\u201340."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"N. Bansal, N. Buchbinder, and J. Naor,\n                      A primal-dual randomized algorithm for weighted paging\n                      , in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Providence, RI, 2007, pp. 507\u2013517.","DOI":"10.1109\/FOCS.2007.43"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/502102.502107"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/050625382"},{"key":"R7","unstructured":"A. Borodin and R. El-Yaniv,\n                      Online Computation and Competitive Analysis\n                      , Cambridge University Press, Cambridge, UK, 1998."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0363"},{"key":"R9","unstructured":"P. Cao and S. Irani,\n                      Cost-aware WWW proxy caching algorithms\n                      , in Proceedings of the USENIX Symposium on Internet Technologies and Systems, 1997, pp. 193\u2013206."},{"key":"R10","unstructured":"R. D. Carr, L. K. Fleischer, V. J. Leung, and C. A. Phillips,\n                      Strengthening integrality gaps for capacitated network design and covering problems\n                      , in Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, 2000, pp. 106\u2013115."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"D. Chakrabarty, E. Grant, and J. K\u00f6nemann,\n                      On column-restricted and priority covering integer programs\n                      , in Proceedings of the 14th Conference on Integer Programming and Combinatorial Optimization (IPCO XIV), 2010, pp. 355\u2013368.","DOI":"10.1007\/978-3-642-13036-6_27"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/0404017"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"M. Chrobak, G. Woeginger, K. Makino, and H. Xu,\n                      Caching is hard\u2014Even in the fault model\n                      , in Proceedings of the 18th Annual European Symposium on Algorithms (ESA 2010), 2010, pp. 195\u2013206.","DOI":"10.1007\/978-3-642-15775-2_17"},{"key":"R14","unstructured":"E. Cohen and H. Kaplan,\n                      LP-based analysis of greedy-dual-size\n                      , in Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, 1999, pp. S879\u2013S880."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90041-V"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"S. Irani,\n                      Competitive analysis of paging: A survey\n                      , in Online Algorithms (Dagstuhl 1996), Lecture Notes in Comput. Sci. 1442, Springer, Berlin, 1998, pp. 52\u201373.","DOI":"10.1007\/BFb0029564"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"S. Irani,\n                      Page replacement with multi-size pages and applications to web caching\n                      , in Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, pp. 701\u2013710.","DOI":"10.1145\/258533.258666"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759073"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"R20","unstructured":"N. Young,\n                      On-line caching as cache size varies\n                      , in Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, 1991, pp. 241\u2013250."},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189992"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0124-5"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090779000","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:29:05Z","timestamp":1787336945000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090779000"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1137\/090779000"],"URL":"https:\/\/doi.org\/10.1137\/090779000","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}