Theorem 4.2 — a large reduced cost fixes an arc across error parameters
ProvedCostScaling.StrongPoly.theorem_4_2_arc_fixedcost-scalingminimum-cost-circulationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1strongly-polynomial
Let be a circulation network with and . Let and . Suppose a circulation is ε-optimal with respect to a price function , and an arc satisfies
Then for every ε′-optimal circulation ,
This gives the arc-fixing criterion that underlies Corollary 4.3 and the progress statement of Lemma 4.4.
Formalization Note The bounds and are the standing network assumption on p. 5; is required by the paper's definition of an error parameter. Lean's reused reduced cost has instead of the paper's ; substituting leaves both optimality and the absolute-value test unchanged.
Preamble
import Mathlib import Definitions.Def_CycleCanceling_MinMean_EpsOptimal
Formal statement
namespace CostScaling.StrongPoly
open CycleCanceling.MinMean
variable {V : Type*} [Fintype V] [DecidableEq V]
/-- Theorem 4.2, p. 16: an arc with a sufficiently large absolute reduced cost
has the same flow in a given `ε`-optimal circulation and every `ε'`-optimal
circulation. The paper's standing `m ≥ n - 1 ≥ 1` is explicit. -/
theorem theorem_4_2_arc_fixed (N : CircNetwork V)
(hvertices : 2 ≤ Fintype.card V)
(harcs : Fintype.card V - 1 ≤ N.E.card)
(ε ε' : ℝ) (hε : 0 < ε) (hε' : 0 ≤ ε')
(f : V → V → ℝ) (hf : IsCirculation N f)
(p : V → ℝ) (hfp : IsEpsOptimalWrt N f ε p)
(v w : V) (hvw : (v, w) ∈ N.E)
(hcost : (Fintype.card V : ℝ) * (ε + ε') ≤ |reducedCost N p v w|) :
∀ f' : V → V → ℝ, IsEpsOptimal N f' ε' → f v w = f' v w := by sorry
end CostScaling.StrongPoly
Source
Goldberg & Tarjan, MIT/LCS/TM-333 (July 1987), Theorem 4.2, p. 16; standing network assumption p. 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.