Lemma 2.1, p. 4 — for monotone submodular of curvature with
ProvedCurvatureSubmod.LocalSearch.lemma_2_1curvaturep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1submodular
Let be a finite set and a monotone increasing submodular function with and total curvature at most , i.e. for every . Then for every ,
The left-hand side is the linear function of §6.1; the lemma says that this linear part already captures a fraction of , which is where the curvature enters the guarantee of Theorem 6.1.
Formalization Note The hypothesis is added: the printed lemma is false without it. For (monotone, submodular, nonnegative, curvature ) the left side is ; the proof's last step goes the wrong way. No range of is assumed: for the right side is nonpositive and the statement still holds. Curvature is in product form (see the Setting definition).
Preamble
import Mathlib import Definitions.Def_NonmonotoneSubmod_Shared_Submodular import Definitions.Def_CurvatureSubmod_LocalSearch_Setting
Formal statement
namespace CurvatureSubmod.LocalSearch
/-- Lemma 2.1, p. 4 (proof p. 14), with the added hypothesis `f ∅ = 0`. -/
theorem lemma_2_1 {X : Type} [Fintype X] [DecidableEq X] (f : Finset X → ℝ)
(hf0 : ∀ A, 0 ≤ f A) (hmono : MonoInc f) (hsub : NonmonotoneSubmod.Shared.Submodular f)
(c : ℝ) (hcurv : CurvAtMostInc f c) (hempty : f ∅ = 0) (A : Finset X) :
(1 - c) * f A ≤ ∑ j ∈ A, marg f (Finset.univ.erase j) j := by sorry
end CurvatureSubmod.LocalSearch
Source
Sviridenko, Vondrák, Ward, Optimal approximation for submodular and supermodular optimization with bounded curvature (SODA 2015 version, Oct. 9, 2014), p. 4, Lemma 2.1 (proof p. 14)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.