On Adaptivity Gaps of Influence Maximization under the Independent Cascade Model with Full-Adoption Feedback - Chen, Wei; Peng, Binghui (Proceedings of the 30th International Symposium on Algorithms and Computation (ISAAC'2019), 2019)
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 inarborescences 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.