§2, pp. 348–349 — h^≺(U) = f(U) for every lower ideal U of ≺, and h^≺ ∈ B_f
ProvedSchrijverSFM.Alg.greedy_mem_baseBbase-polytopegreedy-algorithmp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1submodular-function
Let , let be a submodular real function on the subsets of with , and let be a total order on with greedy vector , where . Then
- for every lower ideal of (a set with ), where ;
- belongs to the base polytope:
Every greedy vector is therefore a point of , so every convex combination of greedy vectors, which is how the algorithm stores its current point, lies in . The identity on lower ideals is what makes the Case 1 set a minimizer.
Formalization Note A total order is a permutation of Fin n read as a position map ( iff ).
Preamble
import Mathlib import Definitions.Def_SchrijverSFM_Alg_Setting
Formal statement
namespace SchrijverSFM.Alg
open NonmonotoneSubmod.Shared
theorem greedy_mem_baseB {n : ℕ} (f : Finset (Fin n) → ℝ) (hsub : Submodular f)
(hf0 : f ∅ = 0) (σ : Equiv.Perm (Fin n)) :
(∀ U : Finset (Fin n), IsLowerIdeal σ U → xsum (greedy f σ) U = f U) ∧
greedy f σ ∈ baseB f := 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. 348 (§2, sentence after display (6)) and pp. 348–349 (§2, last paragraph)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.