PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Joseph Seffi Naor, Tomer Tsachor

arXiv:2610.30430v1cs.DS

TL;DR

Weighted paging with time windows has lagged the unweighted setting, whose randomized algorithms achieve O(log k) competitiveness. We separate cache evolution from page-load scheduling and reduce completion to JRP-D with time-dependent opening costs, obtaining an O(log k)-competitive weighted algorithm.

  • Problem

    Overlapping requests make weighted paging with time windows difficult, and the previously known online bound was O(log n log k)-competitive.

    Source: Paging with time windows · p. 2

  • Method

    The approach separates a cache trajectory from its page loads and reduces online completion to JRP-D with time-dependent opening costs.

    Source: §1.2 · pp. 5–7

  • Results

    O(log k)-competitive randomized algorithm for weighted paging with time windows, improving on Gupta et al.’s O(log k log n) bound.

    Source: §1.1 · p. 5

  • Takeaways & Limitations

    The same O(log k)-competitive guarantee extends to paging with a general delay function.

    Source: §1.2 · p. 8

    The JRP-D analysis assumes power-of-two opening costs; rounding each cost up to a power of two increases any solution’s cost by at most a factor of two.

    Source: §4 · p. 17

Abstract

from arXiv · show

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.

1 Introduction

The paper develops an approach to paging with time windows and delays that separates cache evolution from page-load scheduling and relates scheduling to JRP-D with time-dependent opening costs. It also extends the analysis to penalty models with general delay functions.

Paging with time windows.

  • Time windows let algorithms delay service and batch overlapping requests, but these interactions complicate weighted paging, whose best known online bound was O(log n log k).A request is satisfied when its page is in cache at some time within its release-to-deadline interval.Source: Paging with time windows · p. 2

1.1 Our contribution

  • The (C, D) formalism separates end-of-step cache configurations from page loads, including pages loaded only to serve pending requests and immediately evicted.The representation is conceptual and preserves the objective; cost(C) is the minimum cost over feasible completions D of cache trajectory C.Source: §1.1 · p. 4
  • With cache configurations fixed and revealed online, completion becomes JRP-D with time-dependent opening costs, for which a constant-competitive algorithm is possible with limited predictions.For paging, the prediction is the weight of the page whose pending request has the earliest deadline; the resulting completion satisfies cost(C, D) = O(cost(C)).Source: §1.1 · p. 4
  • O(log k)-competitive randomized algorithms for weighted paging with time windows and delays improve the prior O(log n log k) bound for time windows.The time-window result is stated as Theorem 1.2, and the delays result as Theorem 1.3.Source: Paging with time windows · p. 2, §1.1 · p. 5

1.2 Technical overview

  • The additional O(log n) loss in Gupta et al. comes from online scheduling of extra page loads, not from the cache trajectory, which admits a constant-factor offline completion.Their online and offline conversion algorithms produce the same cache configuration at each time step.Source: §1.2 · pp. 5–6
  • The reduction faithfully captures completion up to a constant factor: every completion yields a comparable JRP solution, and every JRP solution can be transformed online into a feasible completion.The reduction models pages as items, request windows as service intervals, and each order’s cost as an opening cost plus the costs of served items.Source: §1.2 · p. 6
  • The analysis extends to the penalty model and gives an O(log k)-competitive algorithm for paging with a general delay function.This extension uses the same analysis as for paging with time windows.Source: §1.2 · p. 8

2 Our Model and Approach

Paging with time windows lets the algorithm delay service within request intervals, but overlapping requests complicate weighted paging. The approach separates cache evolution from page-load scheduling and uses that decomposition to obtain an O(log k) bound.

2.1 Paging with Time Windows

  • Requests specify a page, release time, and deadline; the objective is to serve every request while minimizing the total weight of page loads.The classical paging problem is the special case where each request’s release time equals its deadline.Source: §2.1 · p. 8

2.2 Prior Work: Gupta et al. [20]

  • Gupta et al. achieve online O(log k) rounding, but feasible-schedule conversion adds O(log n), yielding an O(log k log n)-competitive algorithm.Their offline conversion incurs only an additional O(1) loss.Source: §2.2 · p. 9

2.3 Our Approach

  • The method separates cache evolution C from loads D; once C is revealed online, scheduling feasible loads becomes JRP-D with time-dependent opening costs.Loads that are immediately evicted or implied by cache changes are represented in D, even when they do not appear in the cache trajectory.Source: §2.3 · pp. 9–10

2.4 A Reinterpretation of Gupta et al. [20]

  • O(log k)·OPT bounds cost(C) for an online cache trajectory; completing it online within O(cost(C)) yields an O(log k)-competitive paging algorithm.The cache-trajectory bound follows from Gupta et al.’s online integral solution, while the completion step preserves it up to a constant factor.Source: §2.4 · p. 11

2.5 Joint Replenishment Problem (JRP)

  • With time-varying opening costs, JRP-D has no bounded-competitive online algorithm without future-cost information; prediction values are exposed only for earliest-deadline active requests.The prediction-augmented setting is introduced to address this impossibility.Source: §2.5 · p. 12

3 A Reduction for Completing Cache Configurations

The section reduces online completion of a fixed cache trajectory to JRP-D with time-dependent opening costs, with constant-factor bounds in both directions. A constant-competitive algorithm for that JRP-D variant then yields an O(log k)-competitive algorithm for paging with time windows.

3 A Reduction for Completing Cache Configurations

  • The completion problem is captured up to a constant factor by JRP-D: feasible solutions map in both directions without asymptotic cost loss.The reduction preserves online construction and transformation.Source: §3 · p. 12

3.1 Defining the Instance J(C)

  • J(C) uses page-corresponding items, requests encoding service windows and forced cache-entry loads, and time-dependent opening costs for loads along C.The construction is online: each time-t opening cost and arriving JRP request depends only on history through t.Source: §3.1 · pp. 12–13

3.2 Upper Bounding OPT(J(C))

  • Any feasible paging completion induces a feasible J(C) solution with OPT(J(C)) ≤ 2 · costR(C).The opening-cost definition can overestimate an individual load, but by at most a factor of two.Source: §3.1 · p. 13, §3.2 · p. 14

3.3 From JRP-D Solutions to Paging Solutions

  • A feasible J(C) solution can be converted online into a feasible paging completion by loading its ordered pages and, when needed, a minimum-weight page in the current cache.The added page supports cache consistency and its cost is charged to the JRP opening cost.Source: §3.3 · p. 15

3.4 Consequences for Paging with Time Windows

  • O(log k)-competitive paging with time windows follows from a constant-competitive online algorithm for JRP-D with time-dependent opening costs.The reduction also gives an online completion whose cost is O(costR(C)).Source: §3.4 · p. 16

4 JRP-D with Time-Dependent Opening Costs

The section presents a constant-competitive online algorithm for JRP-D with time-dependent opening costs. Its analysis charges services with deadlines within an OPT phase to nearby OPT costs, and later-deadline services to the next OPT opening cost.

4.1 Algorithm

  • The algorithm combines deadline-driven batching with predictions of future opening costs to handle opening-cost variability.It processes active items by deadline, greedily batching within the current opening cost before using predictions to consider additional items.Source: §4 · p. 17, §4.1 · p. 17

4.2.1 Bounding the Cost of M

  • For M, services whose active deadlines fall before the next OPT order, item costs charge to OPT item costs and opening costs are bounded by a constant multiple of OPT cost.The proof charges each M item service at most twice and separately bounds the opening cost of the last order serving M.Source: §4.2 · p. 18, §4.2.1 · pp. 18, 20

4.2 Competitive Analysis

  • O(1)-competitive is the guarantee for the algorithm for JRP-D with time-dependent opening costs.Opening costs are rounded up to powers of two, increasing any solution cost by at most a factor of two.Source: §4 · p. 17, §4.2 · p. 18

4.2.2 Bounding the Cost of N

  • For N, services with deadlines at or beyond the next OPT order have opening costs that increase as powers of two and remain below that OPT opening cost.Their total opening and item costs are O(oh), charged to OPT's order at h.Source: §4.2.2 · p. 22

AI Usage Disclosure

The authors report that ChatGPT assisted with refining and polishing the text; they reviewed and edited all suggestions and take responsibility for the manuscript.

AI Usage Disclosure

  • The authors used ChatGPT to refine and polish the text, then reviewed and edited its suggestions and retained responsibility for the manuscript.Source: AI Usage Disclosure · p. 22

Submission History

The paper reports an earlier conference submission in July 2026.

Submission History

A Extension to Paging with Delays

The extension handles paging with delays through a penalty version and an online partition of requests. It yields an O(log k)-competitive online algorithm.

A Extension to Paging with Delays

  • In the penalty variant, each request is served within its window or left unserved for its request-specific penalty; Gupta et al. [20] extend their analysis to this variant.The objective minimizes service costs plus penalties for unserved requests.Source: A Extension to Paging with Delays · p. 25
  • The online conversion partitions requests into R1, whose penalties are paid, and R2, represented by page requests served at their first online service time.Both sets can be constructed online.Source: A Extension to Paging with Delays · p. 25
  • The offline conversion preserves cache trajectory C, serves every request in R2 at total cost O(X), and pays penalties for requests in R1.It only removes some load-and-evict steps while remaining feasible for requests served by the online procedure.Source: A Extension to Paging with Delays · p. 25
  • O(log k)-competitive online algorithm for paging with delays follows by combining the penalty bound with the integral solution bound.The penalties for requests in R1 total O(X), and the resulting solution has total cost O(X).Source: A Extension to Paging with Delays · p. 25

B A Local Repair of Cache Trajectories

A feasible paging solution can be modified at no additional cost so that a page from a specified active request set is cached at the set's deadline.

B A Local Repair of Cache Trajectories

  • At time t2, the cache can contain the page of some request in Q without increasing the solution cost.This applies when Q is nonempty, its requests are active at t1 with deadline t2, and no active or unrevealed request outside Q has deadline at most t2.Source: B A Local Repair of Cache Trajectories · p. 26
  • After the last request in Q is served, postponing later loads and evictions until t2 + 1 preserves feasibility, capacity, and cost.The resulting cache configuration persists through t2; if t2 is the final time step, the postponed operations can be omitted.Source: B A Local Repair of Cache Trajectories · p. 26
  • The repair is implementable online by buffering postponed operations and executing them before any newly arriving request with deadline at most t2.Under the lemma's hypothesis, no such request arrives before the cache configuration persists through t2.Source: B A Local Repair of Cache Trajectories · p. 26
Loading 2610.30430v1…