Randomized weighted paging with delay

A cache holds at most k of n pages, and fetching a page has a positive cost. Requests may wait, accumulating delay cost until served. Each request reveals its delay-cost function when it arrives. How close can a randomized online algorithm come to the best schedule that knows all future requests? The target is the total fetch and delay cost, measured by a competitive ratio plus a request-independent additive term.

Why it matters and what counts as progress

Why it matters: Waiting can save fetch costs by serving requests together, but it also creates delay costs. A guarantee depending only on cache size remains useful when the total page collection is much larger than the cache.

What counts as progress: Improve a competitive ratio under stated information and delay assumptions, prove a matching lower bound, or extend an algorithm to a broader delay model. Separate the fractional algorithm, randomized rounding, additive cost and any computational running-time claim.

How the problem developed

2007 · Randomized weighted paging [1]
Nikhil Bansal, Niv Buchbinder and Joseph Naor Gave a primal-dual randomized algorithm for classical weighted paging and an online-rounding theorem. The later delay algorithm uses this rounding theorem, which remains an assumption in its Lean formalization.
2020 · Weighted paging with delay [2]
Anupam Gupta, Amit Kumar and Debmalya Panigrahi Obtained an $O(\log k \log n)$ randomized competitive ratio in the clairvoyant delay model, leaving a gap to the $\Omega (\log k)$ lower bound inherited from classical paging.
17 Oct 2026 · Tight randomized competitive ratio [2][3]
Claude Opus 5.5 with Julian Born, Yann Disser and Linda Thelen Extended the authors’ deadline special cases to general weights and delays using weight classes and preemptive-service budgets. The resulting $O(\log k)$ ratio removes the factor depending on the total number of pages.

Selected milestones in the competitive-ratio question. The independent Nair–Tenenbaum result uses a different approach and is separately credited in the paper.

AI contribution

Tight weighted paging with delay via mirror descent

Julian Born, Yann Disser, Linda Thelen

Born, Disser and Thelen give a randomized online algorithm for weighted paging with delay whose competitive ratio is $O(\log k)$ , matching the classical lower bound. A cache holds k of n pages with positive fetch costs; each request reveals its nondecreasing, continuous, unbounded delay-cost function when it arrives. The expected fetch-plus-delay cost is bounded relative to an optimal offline schedule, with an additive term depending on k and the page weights, not the requests.