Lemma 9, p. 15 — for linear f with f(∅) = 0, f(S) ≥ f(OPT) − Σ_{u∈𝒩} [|O_u| − Y_u] f(u)
ProvedSubsampleSubmod.SampleGreedy.lemma_9greedy-algorithmslinear-objectivesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1submodular-maximization
Let be linear with , an independence system, (playing the role of OPT) and any outcome of the coins. For the final sets of Algorithm 2 run from , let if was added to and at the beginning of the iteration in which was considered, and otherwise. Then
This is the sharper analogue of Lemma 6 for linear objectives, used in the proof of the -approximation.
Formalization Note The hypothesis is added. As printed, without it, the inequality is false for linear functions with : when an element leaves the value drops by , not by , and is possible. A five-element instance with gives . Theorem 1's linear clause does not carry this hypothesis. is computed in .
Preamble
import Mathlib import Definitions.Def_SubsampleSubmod_SampleGreedy_Analysis
Formal statement
namespace SubsampleSubmod.SampleGreedy
/-- Lemma 9 (p. 15), with `f(∅) = 0` added. For linear `f` with `f(∅) = 0` and the final sets of
Algorithm 2 run from an independent `T` (OPT) with coin flips `B`:
`f(S) ≥ f(T) − ∑_{u ∈ 𝒩} (|O_u| − Y_u) f({u})`, where `Y_u = 1` iff `u` is added to `S` and `u ∉ O`
at the beginning of the iteration in which `u` is considered. As printed (without `f(∅) = 0`) the
inequality can fail. -/
theorem lemma_9 {α : Type} [Fintype α] [LinearOrder α] (f : Finset α → ℝ)
(I : Finset α → Prop) (hlin : IsLinear f) (hf_empty : f ∅ = 0) (hI : IsIndepSystem I)
(T : Finset α) (hT : I T) (B : Finset α) :
f T - ∑ u : α, ((((alg2 f I T B).Ou u).card : ℝ) - (if u ∈ (alg2 f I T B).Y then (1 : ℝ) else 0)) *
f {u} ≤
f (alg2 f I T B).S := by sorry
end SubsampleSubmod.SampleGreedy
Source
Harshaw et al., arXiv:2104.02772v1, p. 15, Lemma 9 (definition of Y_u, p. 15; proof pp. 15–16)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.