Display (22), §5, p. 352 — every new arc (v, w) ∈ A′ \ A satisfies s ≼₁ w ≺₁ v ≼₁ t
ProvedSchrijverSFM.Alg.new_arcs_in_intervaldigraphp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1running-timesubmodular-minimization
Let be one iteration of the algorithm with chosen elements and chosen order (the -th order of , with weight ). Let and be the arc sets of the digraphs of and . Then for each arc ,
New arcs arise only from the moved orders and lie inside the interval of . This is the key structural fact of the running-time analysis: it shows that distances never decrease (20) and that no new arc enters .
Formalization Note The order and its weight are named through the hypothesis that the -th entry of is . No submodularity is needed.
Preamble
import Mathlib import Definitions.Def_SchrijverSFM_Alg_Setting
Formal statement
namespace SchrijverSFM.Alg
open NonmonotoneSubmod.Shared
theorem new_arcs_in_interval {n : ℕ} (f : Finset (Fin n) → ℝ)
(S S' : State n) (t s : Fin n) (i : ℕ) (hstep : StepVia f S S' t s i)
(σ₁ : Equiv.Perm (Fin n)) (lam₁ : ℝ) (hi : S[i]? = some (σ₁, lam₁)) :
∀ v w : Fin n, arc S' v w → ¬ arc S v w →
σ₁ s ≤ σ₁ w ∧ σ₁ w < σ₁ v ∧ σ₁ v ≤ σ₁ t := by sorry
end SchrijverSFM.Alg
Source
Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, J. Combin. Theory Ser. B 80 (2000), p. 352, display (22)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.