Lemma 5.10 — at most 3nm saturating pushes
ProvedCostScaling.Refine.saturating_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 is saturated after the push. With and ordered arcs,
This is the second component of the explicit operation bound.
Formalization Note Saturation is tested in the successor state. The of this report counts directed arcs, including both orientations of each edge.
Preamble
import Mathlib import Definitions.Def_CostScaling_Refine_Run
Formal statement
namespace CostScaling.Refine
/-- Lemma 5.10, p. 23. The paper counts ordered arcs of `E`. -/
theorem saturating_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) :
saturatingPushCount N σ K ≤ 3 * Fintype.card V * N.E.card := by sorry
end CostScaling.Refine
Source
Goldberg & Tarjan, MIT/LCS/TM-333 (July 1987), Lemma 5.10, 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.