§3.3, p. 17 — truncated-sketch coverage is monotone submodular
ProvedCostlySeeding.EdgeQuery.submodularedge-queriesindependent-cascadeinfluence-maximizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-algorithms
For any fixed output of PROBE with positive sampling rate , a positive number of copies and positive truncation threshold , the truncated-sketch objective is a monotone submodular function of the seed set. In particular, for seed sets and arbitrary seed sets ,
These are the structural properties needed for the stochastic-greedy approximation guarantee.
Formalization Note The page explicitly states submodularity; monotonicity is included because the same coverage representation gives it.
Preamble
import Definitions.Def_CostlySeeding_EdgeQuery_Algorithm
Formal statement
namespace CostlySeeding.EdgeQuery
theorem submodular (n T tau : ℕ) (hT : 0 < T) (htau : 0 < tau)
(G : SimpleGraph (Fin n)) [DecidableRel G.Adj]
(Vrho : Finset (Fin n)) (rho : ℝ) (hrho : 0 < rho)
(ss : Fin T → ProbeSeed n) :
MonotoneSet (GamCut G Vrho rho tau ss) ∧
SubmodularSet (GamCut G Vrho rho tau ss) := by sorry
end CostlySeeding.EdgeQuery
Source
Eckles, Esfandiari, Mossel & Rahimian, Seeding with Costly Network Information, arXiv:1905.04325v5, p. 17, §3.3 paragraph before Lemma 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.