In a constructed instance with two cache slots, the unrestricted optimum costs 5/2, whereas every schedule using physical farthest-next-use victims costs at least 3. The formal counterexample shows that this victim rule is not always optimal for the delayed problem; it does not estimate how often the rule fails.
The result comes from an arXiv version-1 preprint dated 26 Aug 2026. The paper asks what algorithmic structure remains when a paging miss may wait under a per-replacement maximum-delay model. In its unit-cost setting, a missed page can remain pending. Loading a page costs one movement unit plus the age of its oldest outstanding request, and clears all requests waiting for that page. Delay is therefore part of the replacement cost in the model.
Exact answers depend on the cache configuration
The analysis narrows the offline search without changing the exact optimization target under the stated model. A causal lazy projection reduces the schedules that need to be considered to those that load only pages with pending requests. In the one-hole case, meaning that one empty position is available for a replacement, a dynamic program solves the offline optimum exactly in O(nk) time. It uses 2(k+1) states at each arrival epoch and O(k) working space.
The paper also gives an exact configuration algorithm when the number of holes is any fixed value r. Its running time is m^O(r) poly(n), and the result is classified as XP rather than fixed-parameter tractable, or FPT. That distinction matters because the exact complexity for an unrestricted number of holes remains unresolved.
For every finite page universe and cache size, the paper proves a deterministic, nonproactive polynomial-time 5-approximation for the unit-cost problem. In ordinary terms, its cost is guaranteed to be no more than five times the offline optimum under the formal model. This is an approximation guarantee, not an exact solution to the unrestricted-hole case.
Online bounds remain recognizable
The online results are stated as worst-case guarantees. For general page universes, deterministic Timer-LRU is (5k+3)-competitive, while randomized AW-Partition is 5Hk-competitive against an oblivious adversary, meaning the request sequence is not adapted to the algorithm’s random choices. Here k is the cache size and Hk is the harmonic-number factor in the randomized bound. Both orders are asymptotically tight in the analysis.
With one hole, Timer-LRU has a k+3 bound. Service-anchored Marker has expected cost at most 6Hk times the offline optimum, plus 2Hk+2, under the claim’s randomized guarantee against an oblivious adversary. These are theoretical competitive bounds for the stated delayed-paging model.
Unequal fetch costs add a second source of difficulty
The weighted version tracks how widely fetch costs are spread, using ρ for that spread. The general weighted problem has a deterministic offline approximation of 3ρ+2, a deterministic online bound of O(ρk), and a randomized online bound of O(ρ log k) against an oblivious adversary. The guarantees therefore depend on the range of fetch weights rather than only on cache size.
A separate lower-bound construction shows that weight spread cannot simply be removed from the randomized analysis. For ρ≥2, a two-page instance with one cache slot gives every randomized online algorithm a fixed-input ratio of at least (√ρ−1/√ρ)/2, and therefore at least √ρ/4. The general upper and lower results do not meet: the upper bound grows on the order of ρ, while the cache-one lower bound grows with the square root of ρ.
What the results leave open
Taken together, the preprint reports a split picture. In unit-cost online paging, the deterministic and randomized orders remain asymptotically tight, even though physical farthest-next-use is not always optimal in the delayed offline setting. Exact procedures are available for one hole and for each fixed number of holes, and the general unit-cost problem has a deterministic factor-five approximation. The unrestricted exact complexity remains unresolved, while the weighted results leave a gap between the O(ρ) upper bound and the Ω(√ρ) lower bound at cache size one.
Paper data and sources
Original title: Paging with Per-Replacement Maximum Delay
Authors: Tianhang Lu, Runtian Ren, Shengcai Liu
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text