๐Ÿ“–
Tight Bounds for Paging with Time Windows and Joint Replenishment with Varying Opening Costs
Joseph Seffi Naor, Tomer Tsachor

Tight Bounds for Paging with Time Windows and Joint Replenishment with Varying Opening Costs

Author / Organization:
Science & Mathematics Published 2026 Verification Pending

Overview & Synopsis

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.

Indexed from repository: arXiv (arxiv.org)
Loading document from verified source...
Keyboard Shortcuts: ← / → for pages • + / - for zoom • 0 to fit width Powered by Mozilla PDF.js v3.11

Document Information

Document Title Tight Bounds for Paging with Time Windows and Joint Replenishment with Varying Opening Costs
Author / Organization Joseph Seffi Naor, Tomer Tsachor
Subject & Discipline cs.DS
Categories Science & Mathematics
Publication Year 2026
License / Rights arXiv Open Access / Creative Commons
Resource Verification Listed PDF (Verification Pending)
Original Host Website arXiv (arxiv.org)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-266074
Original Source Link Visit Source Page on arxiv.org »