Speaker
Description
Sharat Ibrahimpur, Manish Purohit, Zoya Svitkina, Erik Vee and Joshua Wang
Abstract: 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 novel potential function to upper bound the cost of an online algorithm paired with a new dual-fitting technique 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.~\cite{ibrahimpur2022caching} and give an $O(\log k)$-competitive fractional online algorithm via a marking strategy. 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.