Optimal algorithm improves caching with timed delays and costs
Tight Bounds for Paging with Time Windows and Joint Replenishment with Varying Opening Costs
Data Structures and Algorithms
Summary
The paper studies a problem where computer systems have to keep pages (pieces of information) ready to use, but each request to access a page must happen within a certain time window. The authors find a better way to decide when to load pages so that the total cost is as low as possible, even when different pages have different importance or weights. They link this problem to a supply chain problem called Joint Replenishment with deadlines and create an algorithm that achieves the best known performance. This improvement could help systems handle time-restricted requests more efficiently.
What this means in practice
- •For network schedulers: Schedule data packets that must arrive within time windows with minimal buffer costs using the improved paging strategy.
- •For supply chain planners: Optimize order timing and batch deliveries with varying costs informed by the joint replenishment algorithm variant.
Authors
Joseph Seffi Naor, Tomer Tsachor
Abstract
We study the paging with time windows problem, a natural generalization of classical paging, in which each request must be served within a specified time interval. This model allows the algorithm to delay service and batch service requests over time, but also introduces significant challenges due to overlapping requests. While the problem is well understood in the unweighted setting, where optimal $O(\log k)$-competitive algorithms are known, the weighted case remains more elusive. The best previously known algorithm, due to Gupta, Kumar, and Panigrahi, achieves an $O(\log k \log n)$-competitive ratio, leaving a gap between weighted and unweighted settings. We obtain an $O(\log k)$-competitive algorithm for weighted paging with time windows, matching the optimal competitive ratio. The core of our approach is a structural decomposition that separates the evolution of the cache from the scheduling of page loads. We show that, given a sequence of cache configurations, computing a near-optimal sequence of page loads reduces to a variant of the Joint Replenishment Problem with deadlines (JRP-D) with time-dependent opening costs. We design a constant-competitive online algorithm for this variant and prove that the reduction is tight. Combining this with an existing online construction of cache configurations yields the desired bound.