Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7.1 — full fractional weighted caching guarantee

Proved
CompetitiveOnlinePD.WeightedCaching.fractional_caching_competitive

by mikedeng1 · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-optimizationonline-algorithmsweighted-caching

Let PPP be a finite universe of unit-size pages, let k≥1k\ge1k≥1 be an integer, and let cp≥1c_p\ge1cp​≥1 be arbitrary real costs. A finite request list has no prescribed horizon or restriction on repetitions or on ∣P∣|P|∣P∣ relative to kkk. All states below are computed by the shared prefix algorithm. Write S(p,j)S(p,j)S(p,j) for its interval slack, DDD for its unscaled dual objective, and L=1+ln⁡kL=1+\ln kL=1+lnk.

The prefix-defined fractional caching algorithm completes every request at its first capacity-satisfying finite real clock. An initially satisfied row causes no update. Each stopping set used is nonempty, bounded below and attains its infimum. At every prefix the interval assignment is LP-feasible, resident fractions lie in [0,1][0,1][0,1], the requested page is fully resident and total resident mass is at most kkk. Existing coordinates increase monotonically, closed coordinates stay frozen, and future dual coordinates remain zero. States at a revealed prefix agree across all continuations.

For every finite prefix HHH and every fractional assignment uuu satisfying its capacity rows and 0≤u≤10\le u\le10≤u≤1,

Calg(H)≤2(1+ln⁡k)C(u).C_{\rm alg}(H)\le 2(1+\ln k)C(u).Calg​(H)≤2(1+lnk)C(u).

At every live state the algorithm also satisfies the full live (7.4):

∑p∈B(t)∖(B′∪{pt})x~(p,r(p,t))≤∣B(t)∣−k−∣B′∣,\sum_{p\in B(t)\setminus(B'\cup\{p_t\})}\widetilde x(p,r(p,t))\le |B(t)|-k-|B'|,p∈B(t)∖(B′∪{pt​})∑​x(p,r(p,t))≤∣B(t)∣−k−∣B′∣,

with B′B'B′ and x~\widetilde xx evaluated at that same state, including a pre-stop event side when unsatisfied.

The primary inequality uses eviction charges. For the independently computed fetching ledger FalgF_{\rm alg}Falg​ and terminal weighted resident mass RalgR_{\rm alg}Ralg​, the goal also states

Falg−Calg=Ralg,0≤Ralg≤∑pcp,F_{\rm alg}-C_{\rm alg}=R_{\rm alg},\qquad 0\le R_{\rm alg}\le\sum_p c_p,Falg​−Calg​=Ralg​,0≤Ralg​≤p∑​cp​,

and

Falg≤2(1+ln⁡k)(C(u)+R(u))+∑pcp.F_{\rm alg}\le 2(1+\ln k)\big(C(u)+R(u)\big)+\sum_p c_p.Falg​≤2(1+lnk)(C(u)+R(u))+p∑​cp​.

Here C(u)+R(u)C(u)+R(u)C(u)+R(u) is the corresponding offline fetching cost. This supplies the sequence-independent additive term allowed by §2.3. The empty prefix, k=1k=1k=1, repeated requests, unequal real costs and k≥∣P∣k\ge|P|k≥∣P∣ are all included. No stopping, feasibility, slackness or competitive guarantee is assumed.

Differences from the source:

  • encoding: finite unit-page universes and arbitrary request prefixes → a finite page type, finite lists and one-based natural indices restricted to valid requests and occurrence intervals; reason: every finite prefix is included, also the empty list; no final horizon or future request is an input to a transition
  • encoding: the next request time in the interval sums → the absent next occurrence is T+1 solely as a summation sentinel; reason: last intervals include all intervening requests through T; the sentinel is never a request
  • reading: the boxed parenthetical r(p_t,t) < t′ < r(p_t,t)+1 → updates between occurrence request times t(p,j)+1 and t(p,j+1)-1; reason: the consecutive counters admit no integer update time; printed p.152 specifies the intended lifetime
  • encoding: continuous updates until capacity is satisfied → an exact real scalar flow with simultaneous events, first-stop infimum and left/right activation states; reason: this gives the stated zero, jump, exponential and saturation rules without discretization; completion is a conclusion
  • reading: no visible operator between the two printed dual-objective sums → the second sum is subtracted; reason: equation (7.8), the dual constraints and the dual-profit derivatives fix the minus sign
  • encoding: inconsistent dummy page letters i,p and an overloaded time t → bound page variables and distinct horizon and row times; reason: the capacity rows and (7.6) bind the intended variables without changing any instance
Preamble
import Definitions.Def_CompetitiveOnlinePD_WeightedCaching_Observables
Formal statement
namespace CompetitiveOnlinePD.WeightedCaching
open scoped BigOperators

theorem fractional_caching_competitive
    {P : Type} [Fintype P] [DecidableEq P]
    (k : ℕ) (hk : 1 ≤ k) (c : P → ℝ) (hc : ∀ p, 1 ≤ c p)
    (H : List P) :
    (∀ (h : List P) (p : P), completes k c h p) ∧
    (∀ h : List P, feasible k h (run k c h).x ∧
      (∀ p, 0 ≤ resident h (run k c h).x p ∧ resident h (run k c h).x p ≤ 1) ∧
      (∑ p, resident h (run k c h).x p) ≤ (k : ℝ)) ∧
    (∀ (h : List P) (p : P), resident (h ++ [p]) (run k c (h ++ [p])).x p = 1) ∧
    (∀ (h tail : List P) (v : P × ℕ), v ∈ intervals h →
      (run k c h).x v.1 v.2 ≤ (run k c (h ++ tail)).x v.1 v.2) ∧
    (∀ (h tail : List P) (p : P) (j : ℕ), 1 ≤ j → j < h.count p →
      (run k c (h ++ tail)).x p j = (run k c h).x p j ∧
      (run k c (h ++ tail)).z p j = (run k c h).z p j) ∧
    (∀ (h : List P) (p : P) (a b : ℝ) (beforeA beforeB : Bool),
      row (h ++ [p]) (h.length+1) (introduce h p (run k c h)).x <
        required k (h ++ [p]) →
      0 ≤ a → a < b → b ≤ duration k c h p (run k c h) →
      ∀ v ∈ intervals (h ++ [p]),
        (clock beforeA k c h p (run k c h) a).x v.1 v.2 ≤
          (clock beforeB k c h p (run k c h) b).x v.1 v.2) ∧
    (∀ (h : List P) (s : State P), reached k c h s →
      (∀ v ∈ intervals h, 0 ≤ s.x v.1 v.2 ∧ s.x v.1 v.2 ≤ 1) ∧
      (∀ t, h.length < t → s.y t = 0)) ∧
    (∀ (h tail : List P) (t : ℕ), t ≤ h.length →
      run k c ((h ++ tail).take t) = run k c (h.take t)) ∧
    (∀ (h : List P) (p : P) (τ : ℝ) (before : Bool), live before k c h p τ →
      liveInequality k (h ++ [p]) (clock before k c h p (run k c h) τ)) ∧
    (∀ u : IntervalArray P, feasible k H u →
      cost c H (run k c H).x ≤ 2 * (1 + Real.log (k : ℝ)) * cost c H u) ∧
    fetchingCost k c H - cost c H (run k c H).x =
      residentValue c H (run k c H).x ∧
    (0 ≤ residentValue c H (run k c H).x ∧
      residentValue c H (run k c H).x ≤ ∑ p, c p) ∧
    (∀ u : IntervalArray P, feasible k H u →
      fetchingCost k c H ≤
        2 * (1 + Real.log (k : ℝ)) * (cost c H u + residentValue c H u) + ∑ p, c p) := by sorry

end CompetitiveOnlinePD.WeightedCaching
Source
Buchbinder & Naor, The Design of Competitive Online Algorithms via a Primal-Dual Approach, copyright 2009, DOI:10.1561/0400000024, https://doi.org/10.1561/0400000024, Theorem 7.1, printed p.154 (PDF p.65), proof through printed p.158 (PDF p.69); §7.1.1 eviction convention printed p.151 (PDF p.62); §2.3 printed pp.107–108 (PDF pp.18–19); live (7.4) printed p.156 (PDF p.67)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me