Lemma 3, p. 410 — level drift along an arc of E⁺
ProvedUnitCapMCF.Excess.lemma3_dlevel_driftcost-scalingexcessminimum-cost-flowp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be -optimal at entry prices , and let be -optimal at current prices , where . Write and . For every ,
The level drift bound is the path constraint used to turn the level bands in Lemma 5 into excess–deficit cuts.
Formalization Note Both optimality predicates include the pseudoflow constraints. No circulation, unit-capacity or integrality assumption is needed for this lemma.
Preamble
import Mathlib import Definitions.Def_UnitCapMCF_Excess_Setting
Formal statement
namespace UnitCapMCF.Excess
/-- Goldberg et al., STACS 2015, Lemma 3, p. 410. -/
theorem lemma3_dlevel_drift {V : Type*} [Fintype V] [DecidableEq V]
(N : CostScaling.Refine.Network V) (ε : ℝ) (hε : 0 < ε)
(f' f : V → V → ℝ) (p' p : V → ℝ)
(hf' : CostScaling.Refine.IsEpsOptimal N (2 * ε) f' p')
(hf : CostScaling.Refine.IsEpsOptimal N ε f p)
(v w : V) (hvw : (v, w) ∈ Eplus N f' f) :
dlevel ε p' p v ≤ dlevel ε p' p w + 3 := by sorry
end UnitCapMCF.Excess
Source
Goldberg, Kaplan, Hed & Tarjan, Minimum Cost Flows in Graphs with Unit Capacities, STACS 2015 (LIPIcs 30), p. 410, Lemma 3; https://doi.org/10.4230/LIPIcs.STACS.2015.406
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.