Lemma 5.9 — at most 3n(n − 1) relabelings
ProvedCostScaling.Refine.relabel_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 be the number of relabel operations among its updates. If , then
This is the first component of the explicit bound on the number of update operations.
Formalization Note counts actual relabel steps in a run from Figure 4's initialization. The parameter is the value after halving. The natural subtraction is zero at , where no relabel step is possible.
Preamble
import Mathlib import Definitions.Def_CostScaling_Refine_Run
Formal statement
namespace CostScaling.Refine
/-- Lemma 5.9, p. 23. -/
theorem relabel_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) :
relabelCount N ε σ K ≤ 3 * Fintype.card V * (Fintype.card V - 1) := by sorry
end CostScaling.Refine
Source
Goldberg & Tarjan, MIT/LCS/TM-333 (July 1987), Lemma 5.9, 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.