Lemma 3.3: a positive minimum over yields a better set
ProvedGeomRescale.lemma_3_3combinatorial-optimizationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1rescalingsubmodular-function-minimizationvon-neumann-algorithm
Let be submodular with , let , and let satisfy . For , we have
This holds for every order sorted by and every argmin in (4). It is the sliding update of Algorithm 1.
Differences from the source:
- generalization: integer valued (standing assumption of Section 3) → and real; reason: the proof uses no integrality; apply it to
fR fand an integer for the page's statement - encoding: → ; reason: is compact and nonempty, so the two conditions agree
Preamble
import Mathlib import Definitions.Def_NonmonotoneSubmod_Shared_Submodular import Definitions.Def_SchrijverSFM_Alg_Setting import Definitions.Def_GeomRescale_IsSortedBy import Definitions.Def_GeomRescale_IsMinSet import Definitions.Def_GeomRescale_enlarge open NonmonotoneSubmod.Shared open SchrijverSFM.Alg
Formal statement
namespace GeomRescale
/-- Lemma 3.3 (Dadush, Végh & Zambelli, Geometric Rescaling Algorithms for Submodular Function Minimization, arXiv:1707.05065v4, Lemma 3.3, p.7): for `μ ≥ max {0, −f(V)}` and `w : V → ℝ` with
`min {wᵀx : x ∈ B(f_μ)} > 0`, every `S = MinSet(f_μ, w)` has `f(S) < −μ`.
**Formalization Note.** The positive minimum is written `∀ x ∈ B(f_μ), 0 < wᵀx`, which is the same
condition as `B(f_μ)` is compact and nonempty. The statement holds for every order `σ` sorted by `w`
and every argmin of (4). -/
theorem lemma_3_3 {n : ℕ} (f : Finset (Fin n) → ℝ) (hsub : Submodular f) (hf0 : f ∅ = 0)
(μ : ℝ) (hμ : max 0 (-f Finset.univ) ≤ μ) (w : Fin n → ℝ)
(hw : ∀ x ∈ baseB (enlarge f μ), 0 < w ⬝ᵥ x)
(σ : Equiv.Perm (Fin n)) (hσ : IsSortedBy w σ) (S : Finset (Fin n))
(hS : IsMinSet (enlarge f μ) σ S) :
f S < -μ := by sorry
end GeomRescale
Source
Dadush, Végh & Zambelli, Geometric Rescaling Algorithms for Submodular Function Minimization, arXiv:1707.05065v4, Lemma 3.3, p.7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.