  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. [10] 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.

Data Structures and Algorithms