Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5.3 — Φ ≤ 1 initially, Φ > 0, and serving on some flow path or rejecting never increases Φ

Proved
BNCovPack.Routing.lemma_5_3

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

derandomizationonline-algorithmsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1routing

Let EEE be a non-empty finite set of mmm edges with capacities u(e)>0u(e) > 0u(e)>0, let B=exp⁡(1+ln⁡(2m)/u(min⁡))−1B = \exp(1 + \ln(2m)/u(\min)) - 1B=exp(1+ln(2m)/u(min))−1, and let Φ(T,L,χ,s)\Phi(T, L, \chi, s)Φ(T,L,χ,s) be the potential of Section 5.2. Then:

  1. initially (T=0T = 0T=0, L=0L = 0L=0, χ=0\chi = 0χ=0, s=0s = 0s=0), Φ≤1\Phi \le 1Φ≤1;
  2. Φ>0\Phi > 0Φ>0 in every state;
  3. consider any state (T,L,χ,s)(T, L, \chi, s)(T,L,χ,s) and a request with paths P1,…,PkP_1, \dots, P_kP1​,…,Pk​ whose flows are raised by g1,…,gk≥0g_1, \dots, g_k \ge 0g1​,…,gk​≥0 with ∑jgj≤1\sum_j g_j \le 1∑j​gj​≤1, so that T′=T+∑jgjT' = T + \sum_j g_jT′=T+∑j​gj​ and Le′=Le+∑j:e∈PjgjL'_e = L_e + \sum_{j : e \in P_j} g_jLe′​=Le​+∑j:e∈Pj​​gj​. Then
∃j: gj>0 and Φ(T′,L′,χ+1Pj,s+1)≤Φ(T,L,χ,s)orΦ(T′,L′,χ,s)≤Φ(T,L,χ,s).\exists j:\ g_j > 0 \ \text{and}\ \Phi\big(T', L', \chi + \mathbf 1_{P_j}, s+1\big) \le \Phi(T, L, \chi, s) \quad \text{or} \quad \Phi(T', L', \chi, s) \le \Phi(T, L, \chi, s).∃j: gj​>0 and Φ(T′,L′,χ+1Pj​​,s+1)≤Φ(T,L,χ,s)orΦ(T′,L′,χ,s)≤Φ(T,L,χ,s).

In words: each time the flow of a request is increased, either serving the request on one of its flow paths (a path whose flow was raised) or rejecting it does not increase the potential. This is what makes the online rounding rule well defined and keeps Φ≤1\Phi \le 1Φ≤1 throughout the run.

Formalization Note The third claim is stated for an arbitrary state and an arbitrary admissible flow increase, which is what the paper's argument uses (gj≥0g_j \ge 0gj​≥0, ∑jgj≤1≤B\sum_j g_j \le 1 \le B∑j​gj​≤1≤B). The existence ranges over the request's flow paths, the paths PjP_jPj​ with gj>0g_j > 0gj​>0, as on the page ("serving the request on some flow path").

Preamble
import Mathlib
import Definitions.Def_BNCovPack_Routing_Routing
import Definitions.Def_BNCovPack_Routing_Potential
import Definitions.Def_BNCovPack_Routing_Algorithm
Formal statement
namespace BNCovPack.Routing

/-- Lemma 5.3, Buchbinder–Naor 2009, p. 15. Let `E` be a non-empty finite set of `m` edges with
capacities `u e > 0`, and `B = exp(1 + ln(2m)/u(min)) − 1`.
1. Initially (no flow, no edge used, no request served) `Φ ≤ 1`.
2. `Φ > 0` in every state.
3. Let a request with path list `ps` have its flows raised by `g` (`g[j] ≥ 0` on the `j`-th path,
   `∑_j g[j] ≤ 1`), from any state with total flow `T`, edge loads `L`, edge usage `χ` and `s`
   served requests. Then either serving the request on some flow path (a path `ps[j]` with
   `g[j] > 0`), or rejecting it, gives a potential (computed with the raised flows) at most the
   potential before the increase. -/
theorem lemma_5_3 {E : Type*} [Fintype E] [Nonempty E] [DecidableEq E] (u : E → ℝ)
    (hu : ∀ e, 0 < u e) :
    potential u (roundingScale u) 0 (fun _ => 0) (fun _ => 0) 0 ≤ 1 ∧
    (∀ (T : ℝ) (L : E → ℝ) (χ : E → ℕ) (s : ℕ), 0 < potential u (roundingScale u) T L χ s) ∧
    ∀ (T : ℝ) (L : E → ℝ) (χ : E → ℕ) (s : ℕ) (ps : List (Finset E)) (g : List ℝ),
      g.length = ps.length → (∀ y ∈ g, 0 ≤ y) → g.sum ≤ 1 →
      (∃ Py ∈ ps.zip g, 0 < Py.2 ∧
          potential u (roundingScale u) (T + g.sum) (fun e => L e + pathLoad e ps g)
            (addPath χ Py.1) (s + 1) ≤ potential u (roundingScale u) T L χ s) ∨
      potential u (roundingScale u) (T + g.sum) (fun e => L e + pathLoad e ps g) χ s ≤
        potential u (roundingScale u) T L χ s := by sorry

end BNCovPack.Routing
Source
Buchbinder, Naor, Online Primal-Dual Algorithms for Covering and Packing, Math. Oper. Res. (2009), DOI 10.1287/moor.1080.0363, p. 15, Lemma 5.3 (proof pp. 15–16)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

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