Display (27), §6, p. 354 — g(X) = f(X̄) + c(X̄) is submodular on all subsets of V
ProvedSchrijverSFM.Ring.g_submodularp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1ring-familysubmodular-functionsubmodular-minimization
Let be a finite set and a ring family on with and for all ( the smallest set of containing ). Let be submodular on , the weights of (23) extended modularly to sets, the smallest set of containing , and
as in (26). Then is submodular on all subsets of :
This is display (27). It turns any algorithm minimizing submodular functions on into one that can be run on (and on , since is modular), which is the point of §6.
Formalization Note Submodularity of is the referenced platform definition NonmonotoneSubmod.Shared.Submodular, the inequality (2) on all of Finset V.
Preamble
import Mathlib import Definitions.Def_NonmonotoneSubmod_Shared_Submodular import Definitions.Def_SchrijverSFM_Ring_Setting
Formal statement
namespace SchrijverSFM.Ring
theorem g_submodular {V : Type} [Fintype V] [DecidableEq V]
(C : Set (Finset V)) (hC : IsRingFamily C) (hempty : ∅ ∈ C) (huniv : Finset.univ ∈ C)
(hM : ∀ u v : V, u ≠ v → M C u ≠ M C v) (f : Finset V → ℝ) (hf : SubmodularOn C f) :
NonmonotoneSubmod.Shared.Submodular (g C f) := by sorry
end SchrijverSFM.Ring
Source
Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, J. Combin. Theory Ser. B 80 (2000), p. 354, §6, display (27)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.