Lemma 4.4 — reducing ε by 2n strictly enlarges the fixed-arc set
ProvedCostScaling.StrongPoly.lemma_4_4_fixedArcs_strictcost-scalingminimum-cost-circulationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1strongly-polynomial
Let be a circulation network with and . For and , suppose there is an ε-tight circulation. Then the set of fixed arcs grows strictly:
Every such reduction of the tight error parameter therefore fixes at least one arc that was not fixed before. This is the finite progress measure used in Theorem 4.5.
Formalization Note The printed lemma omits , but without it the claim is false: would assert . Its proof and Figure 3 use the lemma only at positive ε. The bound is the paper's standing network assumption. The set uses the reused ε-optimality convention, equivalent under .
Preamble
import Mathlib import Definitions.Def_CostScaling_StrongPoly_IsEpsTight import Definitions.Def_CostScaling_StrongPoly_fixedArcs
Formal statement
namespace CostScaling.StrongPoly
open CycleCanceling.MinMean
variable {V : Type*} [Fintype V] [DecidableEq V]
/-- Lemma 4.4, p. 17: when the error parameter drops by a factor of `2n`, the
set of fixed arcs grows strictly. Positive `ε` is required by the proof and by
the statement's truth at the boundary. -/
theorem lemma_4_4_fixedArcs_strict (N : CircNetwork V)
(hvertices : 2 ≤ Fintype.card V)
(harcs : Fintype.card V - 1 ≤ N.E.card)
(ε ε' : ℝ) (hε : 0 < ε) (hε' : 0 ≤ ε')
(hscale : ε' ≤ ε / (2 * (Fintype.card V : ℝ)))
(htight : ∃ f : V → V → ℝ, IsEpsTight N f ε) :
fixedArcs N ε ⊂ fixedArcs N ε' := by sorry
end CostScaling.StrongPoly
Source
Goldberg & Tarjan, MIT/LCS/TM-333 (July 1987), Lemma 4.4, p. 17; Section 2.1, p. 5; Section 2.2, p. 7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.