Theorem 1 — O(log k)-competitive weighted paging with delay
ProvedPagingDelay.PMD.theorem_1delayonline-algorithmsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1paging
There is an absolute constant such that, for every number of pages, every , every positive real weight vector , and every initial cache of exactly pages, there are a clairvoyant randomized online algorithm starting at and a constant with
The probability space, algorithm and additive constant are fixed before the request instance. The optimum ranges over all offline schedules. Requests have arbitrary continuous, nondecreasing, unbounded delay functions, zero at zero. Duplicate requests and simultaneous arrivals are permitted. The full-cache case is included. This is the complete competitive existence claim, without a fractional or dyadic restriction.
Differences from the source:
- encoding: finite pages, continuous time, finite requests and instantaneous cache walks → Fin n pages, real times, finite request and event lists, and ENNReal costs; reason: same instances; positive weights reduce every finite-cost offline schedule to finitely many fetches without increasing cost
- reading: O(log k), including cache size one → C log(2k+1) with an absolute C; reason: the paper proves L=log(2k+1); this is comparable to 1+log k for every k≥1, and avoids a zero ratio at k=1
- encoding: randomized algorithms and their expected costs → probability measures, per-seed online maps and measurable total, fetch and delay cost observables; reason: the usual measurability convention for random costs is explicit; expectations are integrals of random variables rather than arbitrary lower integrals
Preamble
import Definitions.Def_PagingDelay_PMD_Model
Formal statement
namespace PagingDelay.PMD
open scoped BigOperators
/-- Julian Born, Yann Disser, Linda Thelen, Tight weighted paging with delay via mirror descent, STOC 2027 submission #453 (October 2026), Theorem 1 — O(log k)-competitive weighted paging with delay, p. 2. -/
theorem theorem_1 :
∃ C : ℝ, 0 < C ∧ ∀ (n k : ℕ), 1 ≤ k → k ≤ n →
∀ (w : Fin n → ℝ), (∀ i, 0 < w i) →
∀ (O₀ : Finset (Fin n)), O₀.card = k →
∃ (A : RandomizedAlgorithm n k w O₀) (c : ℝ), 0 ≤ c ∧
∀ (σ : Instance n), ValidInstance σ →
expectedCost A σ ≤ ENNReal.ofReal (C * Real.log (2 * (k : ℝ) + 1)) * optimum k w O₀ σ +
ENNReal.ofReal c := by sorry
end PagingDelay.PMD
Source
Julian Born, Yann Disser, Linda Thelen, Tight weighted paging with delay via mirror descent, STOC 2027 submission #453 (October 2026), Theorem 1 — O(log k)-competitive weighted paging with delay, p. 2. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/453.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.