Display (16), §4, Case 1, p. 351 — if D has no path from P to N, the set U of vertices that can reach N minimizes f
ProvedSchrijverSFM.Alg.caseOne_minimizesbase-polytopeoptimality-certificatep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1submodular-minimization
Let be a submodular real function on the subsets of with . Let be a state of the algorithm (, , ), let with , and . Suppose has no directed path from to (Case 1), and let be the set of vertices of that can reach by a directed path (of length ). Then
This is the termination condition of the algorithm: when it stops, is a minimizer of .
Preamble
import Mathlib import Definitions.Def_SchrijverSFM_Alg_Setting
Formal statement
namespace SchrijverSFM.Alg
open NonmonotoneSubmod.Shared
theorem caseOne_minimizes {n : ℕ} (f : Finset (Fin n) → ℝ) (hsub : Submodular f)
(hf0 : f ∅ = 0) (S : State n) (hS : Valid S) (h1 : caseOne f S) :
∀ W : Finset (Fin n), f (caseOneSet f S) ≤ f W := 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. 351, §4 Case 1, display (16)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.