Lemma A.1, p. 14 — with is submodular, monotone increasing and nonnegative
ProvedCurvatureSubmod.LocalSearch.lemma_A_1curvaturep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1submodular
Let be a finite set and a monotone increasing submodular function. Define the linear function and the remainder
Then is submodular, monotone increasing, and nonnegative.
This is the decomposition on which the maximization algorithm of §6.1 runs: the local search is applied to the monotone submodular part and the linear part jointly.
Preamble
import Mathlib import Definitions.Def_NonmonotoneSubmod_Shared_Submodular import Definitions.Def_CurvatureSubmod_LocalSearch_Setting
Formal statement
namespace CurvatureSubmod.LocalSearch
/-- Lemma A.1, p. 14: `g = f − ℓ` with `ℓ(A) = Σ_{j∈A} f_{X−j}(j)` is submodular, monotone
increasing and nonnegative. -/
theorem lemma_A_1 {X : Type} [Fintype X] [DecidableEq X] (f : Finset X → ℝ)
(hf0 : ∀ A, 0 ≤ f A) (hmono : MonoInc f) (hsub : NonmonotoneSubmod.Shared.Submodular f) :
NonmonotoneSubmod.Shared.Submodular (gMax f) ∧ MonoInc (gMax f) ∧
∀ A, 0 ≤ gMax f A := 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. 14, Lemma A.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.