AI Proof WatchKeep up with AI contributions

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)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.

You are reading an earlier published revision. Read the current record.

What was already known

Gupta, Kumar and Panigrahi obtained an O(log⁡klog⁡n)O(\log k \log n) randomized competitive ratio. Classical weighted paging without delay has a tight Θ(log⁡k)\Theta (\log k) ratio; the new result removes the extra dependence on the total number of pages.

This revision has no four-dimension assessment. Read the criteria.

AI involvement

The authors supplied proofs for two special cases and a potential-based analysis. Their disclosure credits Claude Opus 5.5 with extending these results to general weights and delays, including explicit weight classes and preemptive-service budgets. The authors directed the work, independently checked the proofs and wrote the paper.

Importance

The algorithm closes the randomized competitive-ratio gap for the stated clairvoyant delay model. It combines mirror descent with budgets for serving other pending requests, extending the human authors’ deadline special cases to general weights and delays.

Technical verification

Formal checking

Born, Disser and Thelen report independently checking all proofs and the Lean model. The pinned artifact reports Lean 4 checking of the competitive theorem; it assumes the published Bansal–Buchbinder–Naor online-rounding theorem. Its fractional analysis does not use that extra axiom. These are source-reported human and machine checks.

Checker
Lean 4 kernel; Born, Disser and Thelen
Scope
Main competitive theorem conditional on published online rounding; full author proof review separately reported
Basis
Reported by the linked checker

Correction and publication history

2026-11-04 · amendment

Remove the repeated checking explanation and give the exact reported competitive bound in its evidence record. Claim, ratings, methods and sources are unchanged; no additional research notification.

Read this published revision
2026-11-04 · publication

Newly resolved positive AI-origin lead: exact general-weight and delay extension, with independent author proof checks and a scoped formal theorem.

Read this published revision