Lemma 3.8:
ProvedGeomRescale.lemma_3_8combinatorial-optimizationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1rescalingsubmodular-function-minimizationvon-neumann-algorithm
Let be an integer valued submodular function with , and let satisfy . Then for every , and
This is the place where integrality of enters the analysis.
Differences from the source:
- generalization: the conclusion → also the bound (12) of the proof; reason: an added conjunct; dropping it gives the printed lemma
- encoding: → ; reason: same condition on a finite family
- encoding: , width as min and max →
sInfandsSup; reason: under these hypotheses is compact, so they are attained
Preamble
import Mathlib import Definitions.Def_NonmonotoneSubmod_Shared_Submodular import Definitions.Def_SchrijverSFM_Alg_Setting import Definitions.Def_GeomRescale_fR import Definitions.Def_GeomRescale_enlarge import Definitions.Def_GeomRescale_Ltwo import Definitions.Def_GeomRescale_Fmu import Definitions.Def_GeomRescale_width import Definitions.Def_GeomRescale_omega open NonmonotoneSubmod.Shared open SchrijverSFM.Alg
Formal statement
namespace GeomRescale
/-- Lemma 3.8 (Dadush, Végh & Zambelli, Geometric Rescaling Algorithms for Submodular Function Minimization, arXiv:1707.05065v4, Lemma 3.8, p.11, with display (12)): if `f` is an integer valued submodular
function and `μ ∈ ℤ` satisfies `min_{S ⊆ V} f(S) < −μ ≤ min {0, f(V)}`, then
`width_{F_μ}(x) ≥ 1/√n` for every `x ∈ B(f_μ)`, and `ω_μ ≥ 1/(4nL_{f,2})`.
**Formalization Note.** `min_S f(S) < −μ` is written `∃ S, f S < −μ`. The bound (12) is a step of the
proof, kept as a conjunct. -/
theorem lemma_3_8 {n : ℕ} (f : Finset (Fin n) → ℤ) (hsub : Submodular (fR f)) (hf0 : f ∅ = 0)
(μ : ℤ) (hmin : ∃ S, f S < -μ) (hμ : -μ ≤ min 0 (f Finset.univ)) :
(∀ x ∈ baseB (enlarge (fR f) (μ : ℝ)), 1 / √(n : ℝ) ≤ width (Fmu (fR f) (μ : ℝ)) x) ∧
1 / (4 * (n : ℝ) * Ltwo (fR f)) ≤ omega (fR f) (μ : ℝ) := by sorry
end GeomRescale
Source
Dadush, Végh & Zambelli, Geometric Rescaling Algorithms for Submodular Function Minimization, arXiv:1707.05065v4, Lemma 3.8, p.11, and display (12)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.