Lemma 5.11 — at most 3n²(m + n) nonsaturating pushes
ProvedCostScaling.Refine.nonsaturating_push_count_lecost-scalingminimum-cost-circulationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1push-relabel
For any run of generic refine entered with a -optimal circulation and , let count pushes for which the selected arc still has positive residual capacity after the push. With and ordered arcs,
This is the third component of the explicit operation bound.
Formalization Note Nonsaturation is tested in the successor state, and the parameter is the value after the entry parameter is halved.
Preamble
import Mathlib import Definitions.Def_CostScaling_Refine_Run
Formal statement
namespace CostScaling.Refine
/-- Lemma 5.11, pp. 23–24. -/
theorem nonsaturating_push_count_le {V : Type*} [Fintype V] [DecidableEq V]
(N : Network V) (ε : ℝ) (hε : 0 < ε)
(f₀ : V → V → ℝ) (p₀ : V → ℝ)
(hcirc : CycleCanceling.MinMean.IsCirculation N f₀)
(hentry : IsEpsOptimal N (2 * ε) f₀ p₀)
(σ : ℕ → State V) (K : ℕ)
(hrun : IsRun N ε f₀ p₀ σ K) :
nonsaturatingPushCount N σ K ≤
3 * Fintype.card V ^ 2 * (N.E.card + Fintype.card V) := by sorry
end CostScaling.Refine
Source
Goldberg & Tarjan, MIT/LCS/TM-333 (July 1987), Lemma 5.11, p. 23; https://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TM-333.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.