Lemma 5.8 — price increase at most 3nε
ProvedCostScaling.Refine.price_increase_lecost-scalingminimum-cost-circulationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1push-relabel
Let , let , and enter refine with a circulation that is -optimal with respect to . During any run of the generic subroutine, every vertex price is bounded above by its entry value plus :
This price bound limits how often relabel can occur and thus supports the operation counts.
Formalization Note The source's is the parameter after halving. The entry circulation and its -optimality are explicit hypotheses.
Preamble
import Mathlib import Definitions.Def_CostScaling_Refine_Run
Formal statement
namespace CostScaling.Refine
/-- Lemma 5.8, p. 22: the bound uses the error parameter after halving. -/
theorem price_increase_le {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 ≤ K, ∀ v, (σ k).p v ≤ p₀ v + 3 * (Fintype.card V : ℝ) * ε := by sorry
end CostScaling.Refine
Source
Goldberg & Tarjan, MIT/LCS/TM-333 (July 1987), Lemma 5.8, p. 22; 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.