2026-08-17T19:48:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18132 2024-03-06T11:01:06Z ddc:004 open_access

Efficient Caching with Reserves via Marking Ibrahimpur, Sharat Purohit, Manish Svitkina, Zoya Vee, Erik Wang, Joshua R. Approximation Algorithms Online Algorithms Caching Online caching is among the most fundamental and well-studied problems in the area of online algorithms. Innovative algorithmic ideas and analysis - including potential functions and primal-dual techniques - give insight into this still-growing area. Here, we introduce a new analysis technique that first uses a potential function to upper bound the cost of an online algorithm and then pairs that with a new dual-fitting strategy to lower bound the cost of an offline optimal algorithm. We apply these techniques to the Caching with Reserves problem recently introduced by Ibrahimpur et al. [Ibrahimpur et al., 2022] and give an O(log k)-competitive fractional online algorithm via a marking strategy, where k denotes the size of the cache. We also design a new online rounding algorithm that runs in polynomial time to obtain an O(log k)-competitive randomized integral algorithm. Additionally, we provide a new, simple proof for randomized marking for the classical unweighted paging problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sharat Ibrahimpur and Manish Purohit and Zoya Svitkina and Erik Vee and Joshua R. Wang 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.80 urn:nbn:de:0030-drops-181328 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.80 eng https://creativecommons.org/licenses/by/4.0/legalcode