2026-07-25T22:36:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11520 2024-03-06T10:48:13Z ddc:004 open_access

On Adaptivity Gaps of Influence Maximization Under the Independent Cascade Model with Full-Adoption Feedback Chen, Wei Peng, Binghui Adaptive influence maximization adaptivity gap full-adoption feedback In this paper, we study the adaptivity gap of the influence maximization problem under the independent cascade model when full-adoption feedback is available. Our main results are to derive upper bounds on several families of well-studied influence graphs, including in-arborescences, out-arborescences and bipartite graphs. Especially, we prove that the adaptivity gap for the in-arborescences is between [e/(e-1), 2e/(e-1)], and for the out-arborescences the gap is between [e/(e-1), 2]. These are the first constant upper bounds in the full-adoption feedback model. Our analysis provides several novel ideas to tackle the correlated feedback appearing in adaptive stochastic optimization, which may be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Wei Chen and Binghui Peng 2019 Is Part Of LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2019.24 urn:nbn:de:0030-drops-115208 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.24 eng https://creativecommons.org/licenses/by/3.0/legalcode