Generic refine terminates within an explicit update bound at an ε-optimal circulation
ProvedCostScaling.Refine.generic_refine_correct_and_boundedLet be a finite symmetric circulation network with vertices and ordered arcs. Enter generic refine with , a circulation , and prices for which is -optimal. Start from Figure 4's initialized pseudoflow and take any applicable push or relabel steps, in any order. Then:
If the last state still has an active vertex, a further push or relabel step exists. If no operation applies there, its pseudoflow is a circulation and is -optimal with respect to its final prices. Consequently, every choice of applicable operations stops within the displayed bound at an -optimal circulation.
The result gathers the progress and correctness statements of Section 5 and the explicit bounds of Lemmas 5.9–5.11. It is an update count, not a RAM-model running time.
Formalization Note The formal parameter is the error after Figure 4 halves the input ; counts ordered arcs. Termination uses Figure 4's loop guard, and a relabel successor requires an attained minimum over a nonempty residual set.
import Mathlib import Definitions.Def_CostScaling_Refine_Run
namespace CostScaling.Refine
/-- Theorem 5.4 and Lemmas 5.1, 5.9–5.11, with the paper's constants. -/
theorem generic_refine_correct_and_bounded {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) :
K ≤ 3 * Fintype.card V * (Fintype.card V - 1) +
3 * Fintype.card V * N.E.card +
3 * Fintype.card V ^ 2 * (N.E.card + Fintype.card V) ∧
(∀ v, IsActive N (σ K).f v → ∃ t, IsStep N ε (σ K) t) ∧
(Terminated N (σ K) →
CycleCanceling.MinMean.IsCirculation N (σ K).f ∧
IsEpsOptimal N ε (σ K).f (σ K).p) := by sorry
end CostScaling.Refine
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.