B.12, p. 46 — worst-case query count
ProvedCostlySeeding.EdgeQuery.worst_case_queriesedge-queriesindependent-cascadeinfluence-maximizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-algorithms
For any initial vertex set, any threshold, and every realization of the PROBE copies on a graph with vertices, the total query count satisfies
This coarse worst-case bound controls the query count on the exceptional event in the expectation bound (30). It counts both first-chance and discarded second-chance queries.
Preamble
import Definitions.Def_CostlySeeding_EdgeQuery_Algorithm
Formal statement
namespace CostlySeeding.EdgeQuery
theorem worst_case_queries (n T tau : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj]
(Vrho : Finset (Fin n)) (ss : Fin T → ProbeSeed n) :
queries G Vrho tau ss ≤ 2 * T * n ^ 2 := by sorry
end CostlySeeding.EdgeQuery
Source
Eckles, Esfandiari, Mossel & Rahimian, Seeding with Costly Network Information, arXiv:1905.04325v5, p. 46, B.12 paragraph after (30)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.