On Approximating Target Set Selection

DOI10.4230/LIPIcs.APPROX-RANDOM.2016.4zbMath1398.68189OpenAlexW2557748541MaRDI QIDQ4636434

Yonatan Naamad, Anthony Wirth, Moses Charikar

Publication date: 19 April 2018

Full work available at URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.4

zbMATH Keywords

approximation algorithmshardness of approximationtarget set selectioninfluence propagationplanted dense subgraph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Social networks; opinion dynamics (91D30) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (8)

An approximate marginal spread computation approach for the budgeted influence maximization with delay ⋮ Hardness Results for Seeding Complex Contagion with Neighborhoods ⋮ Unique key Horn functions ⋮ On approximating the rank of graph divisors ⋮ Unnamed Item ⋮ Target set selection for conservative populations ⋮ Precedence-Constrained Min Sum Set Cover ⋮ On reconfigurability of target sets

This page was built for publication: On Approximating Target Set Selection