Concavity of on
ProvedStreamSubmod.concavityp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1streaming-algorithmssubmodular-maximization
Let be submodular with multilinear extension , and let . Then the function
is concave on . Comparing the value at with the endpoints gives the bound used in the proof of Lemma 6.
Differences from the source:
- generalization: S = Ŝi and B = OPT \ O → arbitrary sets S, B ⊆ V; reason: the sets of the page are a special case
Preamble
import Mathlib import Definitions.Def_NonmonotoneSubmod_Shared_Submodular import Definitions.Def_NonmonotoneSubmod_Shared_F
Formal statement
namespace StreamSubmod
open NonmonotoneSubmod.Shared in
/-- Concavity (Alaluf, Ene, Feldman, Nguyen & Suh, arXiv:1911.12959v3, proof of Lemma 6, p.9): "the
submodularity of `f` implies that `F((t·𝟏_{Ŝᵢ}) ∨ 𝟏_{OPT\O})` is a concave function of `t` within the
range `[0, 1]`". Stated for arbitrary sets `S`, `B`. -/
theorem concavity {E : Type} [Fintype E] [DecidableEq E] (f : Finset E → ℝ) (hf : Submodular f)
(S B : Finset E) :
ConcaveOn ℝ (Set.Icc (0 : ℝ) 1)
(fun t : ℝ => F f (fun e => max (t * (if e ∈ S then 1 else 0)) (if e ∈ B then 1 else 0))) := by sorry
end StreamSubmod
Source
Alaluf, Ene, Feldman, Nguyen & Suh, An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint, arXiv:1911.12959v3, proof of Lemma 6, p.9, "the submodularity of f implies that F((t·1_Ŝi)∨1_OPT\O) is a concave function of t within the range [0, 1]"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.