Lemma 29 — lightest weights of offline period caches
ProvedPagingDelay.PMD.lemma_29delayonline-algorithmsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1paging
For any lazy feasible offline schedule , let be its cache after the positive-cost walk at the th distinct update time. Excluding the initial period,
Each walk time is counted once, even if it contains several swaps. The empty list of walks gives the empty sum.
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
- generalization: an optimal lazy offline schedule Opt → every lazy feasible offline schedule O, with cost(O) on the right; reason: the source proofs use only laziness and service of every request; an optimal lazy schedule is one such comparator
Preamble
import Definitions.Def_PagingDelay_PMD_Path
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), Lemma 29 — lightest weights of offline period caches, p. 22. -/
theorem lemma_29 (n k : ℕ) (hk : 1 ≤ k) (hkn : k < n)
(w : Fin n → ℝ) (hw : PMDWeights w)
(O₀ : Finset (Fin n)) (hO₀ : O₀.card = k)
(σ : Instance n) (hσ : ValidInstance σ) (O : Schedule n)
(hO : LazyFeasible k O₀ O σ) :
ENNReal.ofReal (((periodCaches O₀ O).map (minWeight w)).sum) ≤ totalCost w O₀ O σ := 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), Lemma 29 — lightest weights of offline period caches, p. 22. 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.