Rounding: a fractional point of -norm at most rounds to a set worth at least
ProvedStreamSubmod.roundingp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1streaming-algorithmssubmodular-maximization
Let be submodular, with multilinear extension , and let satisfy . Then there is a set contained in the support of , with , such that
The proof of Lemma 6 applies this to the vector , citing Pipage Rounding and Swap Rounding. It turns a fractional solution into a feasible input for the guarantee of OfflineAlg.
Differences from the source:
- generalization: the vector (b1_Ŝi) ∨ 1_{OPT\O}, whose support lies in Ŝi ∪ (OPT \ O) → every x ∈ [0,1]^V with ‖x‖₁ ≤ k, and a set inside the support of x; reason: the page uses only ‖x‖₁ ≤ k and this support property, and the instance is 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
/-- Rounding (Alaluf, Ene, Feldman, Nguyen & Suh, arXiv:1911.12959v3, proof of Lemma 6, p.9,
"standard rounding techniques such as Pipage Rounding [13] and Swap Rounding [18] can be used"):
for a submodular `f`, every fractional point `x ∈ [0,1]^E` with `‖x‖₁ ≤ k` can be rounded to a set
`A` inside the support of `x`, with `|A| ≤ k` and `f(A) ≥ F(x)`.
**Formalization Note.** The proof of Lemma 6 applies this to `x = (b𝟏_{Ŝᵢ}) ∨ 𝟏_{OPT\O}`. -/
theorem rounding {E : Type} [Fintype E] [DecidableEq E] (f : Finset E → ℝ) (hf : Submodular f)
(k : ℕ) (x : E → ℝ) (hx0 : ∀ e, 0 ≤ x e) (hx1 : ∀ e, x e ≤ 1)
(hxk : ∑ e, x e ≤ (k : ℝ)) :
∃ A : Finset E, (∀ e ∈ A, 0 < x e) ∧ A.card ≤ k ∧ F f x ≤ f A := 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, "standard rounding techniques such as Pipage Rounding [13] and Swap Rounding [18] can be used"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.