Display (20), §5, pp. 352–353 — distances never decrease: d′(v) ≥ d(v) for all v
ProvedSchrijverSFM.Alg.dist_monotonedigraphp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1running-timesubmodular-minimization
Let be one iteration of the algorithm, and let and be the distance functions of and : is the minimum number of arcs of a directed path in from to , and if there is none. Then
Together with (21), this monotonicity drives the bound: each can increase at most times.
Formalization Note Distances take values in (ℕ∞), with for unreachable vertices. No submodularity is needed.
Preamble
import Mathlib import Definitions.Def_SchrijverSFM_Alg_Setting
Formal statement
namespace SchrijverSFM.Alg
open NonmonotoneSubmod.Shared
theorem dist_monotone {n : ℕ} (f : Finset (Fin n) → ℝ)
(S S' : State n) (t s : Fin n) (i : ℕ) (hstep : StepVia f S S' t s i) :
∀ v : Fin n, dist f S v ≤ dist f S' v := by sorry
end SchrijverSFM.Alg
Source
Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, J. Combin. Theory Ser. B 80 (2000), pp. 352–353, display (20)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.