§6, last paragraph, p. 354 — if U minimizes g(U) − c(U) over all U ⊆ V then Ū minimizes f over 𝒞
ProvedSchrijverSFM.Ring.minimizer_transferminimizerp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1ring-familysubmodular-minimization
Let be a finite set and a ring family on with . Let be any function, the weights of (23) extended modularly to sets, the smallest set of containing , and as in (26). If minimizes over all subsets of , that is,
then and minimizes over :
This is the final step of Schrijver's reduction: a minimizer of the submodular function on , found by the algorithm of §§2–5, yields a minimizer of over the ring family.
Formalization Note Only closure under union and intersection and are used; submodularity of , and are not assumed here (they are needed for (27), not for this transfer).
Preamble
import Mathlib import Definitions.Def_NonmonotoneSubmod_Shared_Submodular import Definitions.Def_SchrijverSFM_Ring_Setting
Formal statement
namespace SchrijverSFM.Ring
theorem minimizer_transfer {V : Type} [Fintype V] [DecidableEq V]
(C : Set (Finset V)) (hC : IsRingFamily C) (huniv : Finset.univ ∈ C)
(f : Finset V → ℝ) (U : Finset V)
(hU : ∀ W : Finset V, g C f U - csum C f U ≤ g C f W - csum C f W) :
closure C U ∈ C ∧ ∀ T ∈ C, f (closure C U) ≤ f T := 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, last paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.