CS Paper Radar

Two Holes Make a Difference: Deterministic Paging with Delay and Deadlines

Darya Melnyk, Linda Thelen, Yuyi Wang

cs.DS ·submitted 2026-10-13 17:28 UTC · v1
theory

Abstract

In this paper, we study online paging with delay or deadlines. In online paging with delay, an online algorithm manages a cache of size $k$ and needs to serve incoming requests by adding the requested pages to the cache. In addition, it has the option to delay serving incoming requests at a cost that depends on the delay. We propose a new online algorithm, which combines a threshold rule with first-in, first-out (FIFO) replacement, and show that it is $(2k+2)$-competitive for cache size $k$. This result corrects a previously published claim that the competitive ratio is exactly $2k+1$ regardless of the number of holes (pages outside the cache). However, in the case of one hole, we show that the FIFO rule with a different threshold is indeed $(2k+1)$-competitive, giving a tight result. In the case of deadlines, the same analysis gives a deadline-triggered algorithm that is $(k+1)$-competitive in general and $k$-competitive if there is only one hole. Moreover, we show that the second hole makes paging with deadlines strictly harder than classical paging, where the competitive ratio is independent of the number of holes. For paging with deadlines, we prove a deterministic lower bound of $k+\tfrac12$, already for two holes. We show that, as a consequence, no threshold-triggered algorithm can achieve a competitive ratio less than $2k+\frac32$ in general.

Closest papers

Nearest neighbours by meaning across the whole index.

Tight Bounds for Paging with Delay and Joint Replenishment with Varying Opening Costs

cs.DS ·2026-10-21 ·Joseph, Naor, Tomer Tsachor
theorycode/data similarity 0.78
Abstract

We study weighted paging with delay, a generalization of classical paging in which requests may be served after their arrival, incurring delay costs while awaiting service. 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 randomized 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 a randomized $O(\log k)$-competitive algorithm, matching the lower bound inherited from classical paging. The core of our approach is a structural decomposition that separates the evolution of the cache over time from scheduling additional page loads, so as to make the solution feasible. We develop this approach first for paging with time windows, the special case in which each request must be served within a specified time interval. Given a sequence of cache configurations, we reduce the problem of augmenting this sequence to a feasible solution 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 under a prediction model whose required information is available online in our paging reduction. Combining this algorithm with an existing online construction of cache configurations yields an $O(\log k)$-competitive algorithm for paging with time windows. We then extend the framework to obtain the same guarantee for weighted paging with a general delay function.

0.36

Paging with Per-Replacement Maximum Delay

cs.DS ·2026-08-26 ·Tianhang Lu, Runtian Ren, Shengcai Liu
theoryhot direction similarity 0.77
Abstract

Classical paging serves every miss immediately. We study paging with per-replacement maximum delay, where loading a pending page costs one movement plus the age of its oldest outstanding request and clears that page's entire episode. Equivalently, the holding rate is the number of pending pages. For cache size $k$, threshold LRU is strictly $(5k+3)$-competitive, while a randomized algorithm is strictly $5H_k$-competitive against an oblivious adversary; classical constructions give matching $Ω(k)$ and $Ω(H_k)$ orders. Offline, we obtain an exact $O(nk)$ dynamic program with one hole, an exact configuration algorithm for any fixed number of holes, and a nonproactive polynomial-time $5$-approximation in general. Physical farthest-next-use can nevertheless fail with only three pages. For page-dependent fetch costs with spread $ρ=w_{\max}/w_{\min}$, the exact fixed-number-of-holes algorithms persist. We obtain a $(3ρ+2)$-approximation and online guarantees with multiplicative factors $O(ρk)$ deterministically and $O(ρH_k)$ randomly against an oblivious adversary, plus any additive term inherited from the corresponding classical guarantee. A strict $Ω(\sqrtρ)$ randomized lower bound already holds for one cache slot. Thus maximum delay preserves the unit-cost competitive hierarchy but disrupts classical offline structure and makes weighted timing spread-sensitive.

0.30

Tight weighted paging with delay via mirror descent

cs.DS ·2026-10-17 ·Julian Born, Yann Disser, Linda Thelen
theory similarity 0.72
Abstract

We give an O(log k)-competitive randomized algorithm for weighted paging with delay. This improves upon the O(log k log n)-competitive algorithm of Gupta, Kumar, and Panigrahi (STOC 2020, SICOMP 2022) by removing the dependence on the number n of pages. Without delay, the optimal competitive ratio of randomized algorithms is Theta(log k), and since the lower bound carries over, our bound is tight. Our algorithm is fractional and combines mirror descent, used by Bubeck et al. (STOC 2018) for weighted paging without delay, with preemptive service, introduced by Azar et al. (STOC 2017) for online service with delay: when a request is served, an increase in the mirror descent potential is offset by preemptive service to other pending requests, with a budget derived from the mirror descent path. To obtain a randomized algorithm, we use the online rounding of Bansal, Buchbinder, and Naor (FOCS 2007) from classical paging.

0.42

List Update with Per-Page Maximum Delay

cs.DS ·2026-11-10 ·Tianhang Lu, Runtian Ren, Shengcai Liu
similarity 0.70
Abstract

We study list update with per-page maximum delay. Requests may wait, and one access clears all pending requests of a page at its current list rank, paying their maximum waiting penalty. Each service can change the permutation and therefore the cost of later accesses. We give a strictly $5$-competitive deterministic algorithm: serve a page when the oldest waiting time reaches two thirds of its current rank, then move it to the front. Our main tool is an asynchronous marked-rank coupling that compares different list orders and different service histories. A temporal transfer principle separates this permutation argument from two waiting-cost inequalities. It gives factor $5$ for page-specific superadditive penalties, common calendar rates, and additional hard deadlines; deadlines alone admit factor $3$. Two structural conditions on request-specific penalties give factor $3+2κ$. In particular, nonincreasing request severity retains factor $5$ even with unbounded weight ratios. For linear delay, offline optimization is NP-complete but fixed-parameter tractable in the number of pages. We characterize fixed-list batching, show an $Ω(m)$ gap between the best static order and dynamic reordering, and prove that the optimal deterministic factor for one page is exactly $2$. Counterexamples delineate the threshold rule's scope.

0.20

Stochastic Weighted Caching with Per-Request Predictions

cs.DS ·2026-10-12 ·Shuchi Chawla, Dimitris Christou
theory similarity 0.69
Abstract

Both the unweighted and weighted variants of caching are cornerstone problems in competitive analysis, with tight randomized competitive ratios of $Θ(\log k)$, where $k$ is the cache size. We study weighted caching with per-request predictions, where each page request is accompanied by a prediction of the next arrival time of the same page. For unweighted caching, such perfect predictions suffice to implement Belady's offline optimal rule. For weighted caching, however, previous work shows that a logarithmic lower bound persists even with perfect predictions on adversarial request sequences. Stochastic assumptions alone are also insufficient: the classical caching lower bounds already apply to uniform independent requests. In this work, we ask whether combining these two sources of additional information can overcome this barrier, and answer this question affirmatively. Specifically, we develop an efficient cache eviction policy that achieves a competitive ratio of $15.75$ using perfect per-request predictions when page requests are drawn independently from an arbitrary, known static distribution in every step, and page costs are arbitrary. Underlying our analysis is a novel lower bound on the optimal cost obtained through an ex-ante relaxation of the cache's covering constraints. Our algorithm's performance degrades gracefully under erroneous predictions: we prove a bound of $O(\min\{1+E,\log k\})$ on the competitive ratio, where $E$ aggregates each page's average prediction error, and may be unknown to the algorithm.

0.22

A Tight Linear Deterministic Competitive Ratio for Fully Online KV-Cache Scheduling

cs.DS ·2026-08-14 ·Ian D'Ambrosio
theory similarity 0.64
Abstract · 6 pages. The exact fully online model, fixed-memory-before-scheduler quantifier order, serial upper bound, and wide-short lower bound are ch…

Jaillet et al. introduced a fully online model for batching nonpreemptive LLM requests under a growing KV-cache memory constraint. For total end-to-end latency they proved that every deterministic algorithm has competitive ratio Omega(sqrt(n)), while the elementary sequential upper bound is n. We close this gap. Let R_det(n,M) be the optimal deterministic ratio for exactly n requests at memory M, and let R_det(n)=sup_M R_det(n,M). For every n >= 2 we prove (n-1)/12 <= R_det(n) <= n, so R_det(n)=Theta(n). The lower bound releases one memory-filling long request, observes its deterministic start time, and then releases n-1 wide one-token requests halfway through the long run. No short request can overlap the long one, whereas a hindsight schedule runs the two groups in the opposite order when useful. The hard instance uses the explicit fixed memory M=2(n-1)n. The upper bound is achieved by a uniform causal serial policy. The exact model, causality argument, both comparator branches, and quantifier order are machine-checked in Lean 4. Exact finite controls and replay commands accompany the proof.

0.07

Online Service with Per-Batch Maximum Delays

cs.DS ·2026-08-19 ·Tianhang Lu, Runtian Ren, Shengcai Liu, Ke Tang
similarity 0.64
Abstract

We study online service with per-batch maximum delays on a finite metric space. Requests arrive over time, and a server serves each batch by following a walk visiting its requests' locations. Movement is instantaneous. The objective is to minimize the total distance traveled by the server plus the sum, over all batches, of the maximum waiting time in each batch. We give deterministic polynomial-time algorithms with competitive ratios $10$ on finite lines, $12$ on weighted trees, and $20$ on arbitrary finite metrics. Unlike additive delay, maximum delay allows younger requests to join a batch without increasing its delay charge. Our algorithms coordinate service using a common waiting clock and a threshold determined by the metric. The analysis uses certificates for groups of requests to compare this policy with any offline schedule, even one that serves different batches and follows different walks. This comparison shows that coordinating service in this way loses only a constant factor. The bounds hold whether the server must serve requests it visits or may leave them unserved; the two rules also have equal offline optimal costs. Offline optimization is polynomial on lines and explicitly represented weighted trees, and NP hard on general metrics. When arrivals are announced but locations are hidden until visited, we give an $84$-competitive algorithm on a known finite line under either rule.

0.13

A General Framework for Matching with Delays

cs.DS ·2026-10-15 ·Sara Ahmadian, Shuchi Chawla, Ravi Kumar, Manish Purohit, Shirley Zhang
theory similarity 0.63
Abstract

We present a simple deterministic $O(\log n)$-competitive algorithm for the online minimum-cost perfect matching with delays (MPMD) problem on arbitrary, unknown metric spaces, where $n$ is the (unknown) number of requests. This improves upon the recent $O(\log^5 n)$-competitive algorithm of Dufay and Wattenhofer (SODA 2026) and nearly matches the $Ω(\log n / \log \log n)$ randomized lower bound of Ashlagi et al. (APPROX 2017). Our algorithmic framework rests on two ingredients: an online moat-growing process that grows active dual variables at a deliberately slowed constant rate $α< 1$ to control temporal asymmetry, and a delayed eligibility rule that matches requests in the same dual component only after their waiting time is proportional to their time-expanded distance. The framework extends naturally to arbitrary concave delay functions, maintaining an $O(\log n)$ competitive ratio, and to $k$-way matching with delays, yielding an $O(k \log n)$-competitive deterministic algorithm.

0.48