Theorem 5.4 — terminated refine returns an ε-optimal circulation
ProvedCostScaling.Refine.terminated_refine_correctcost-scalingminimum-cost-circulationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1push-relabel
Let be a circulation that is -optimal with respect to prices , with . Start generic refine by halving the input error parameter and saturating all arcs of negative reduced cost. Let be any resulting sequence of applicable push and relabel operations. If no operation is applicable in , then its pseudoflow is a circulation and remains -optimal with respect to its final prices :
This is the partial correctness result for the generic subroutine; the update counts separately establish finite termination.
Formalization Note “Terminated” is the literal negation of Figure 4's update guard. The parameter here is the new error parameter after Figure 4 halves the input .
Preamble
import Mathlib import Definitions.Def_CostScaling_Refine_Run
Formal statement
namespace CostScaling.Refine
/-- Theorem 5.4, p. 21, including the entry contract of refine. -/
theorem terminated_refine_correct {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)
(hterm : Terminated N (σ K)) :
CycleCanceling.MinMean.IsCirculation N (σ K).f ∧
IsEpsOptimal N ε (σ K).f (σ K).p := by sorry
end CostScaling.Refine
Source
Goldberg & Tarjan, MIT/LCS/TM-333 (July 1987), Theorem 5.4, p. 21; 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.