Timezone: »
We study the adaptive influence maximization problem with myopic feedback under the independent cascade model: one sequentially selects k nodes as seeds one by one from a social network, and each selected seed returns the immediate neighbors it activates as the feedback available for by later selections, and the goal is to maximize the expected number of total activated nodes, referred as the influence spread. We show that the adaptivity gap, the ratio between the optimal adaptive influence spread and the optimal nonadaptive influence spread, is at most 4 and at least e/(e1), and the approximation ratios with respect to the optimal adaptive influence spread of both the nonadaptive greedy and adaptive greedy algorithms are at least \frac{1}{4}(1  \frac{1}{e}) and at most \frac{e^2 + 1}{(e + 1)^2} < 1  \frac{1}{e}. Moreover, the approximation ratio of the nonadaptive greedy algorithm is no worse than that of the adaptive greedy algorithm, when considering all graphs. Our result confirms a longstanding open conjecture of Golovin and Krause (2011) on the constant approximation ratio of adaptive greedy with myopic feedback, and it also suggests that adaptive greedy may not bring much benefit under myopic feedback.
Author Information
Binghui Peng (Columbia University)
Wei Chen (Microsoft Research)
More from the Same Authors

2021 Poster: Dynamic influence maximization »
Binghui Peng 
2021 Poster: Combinatorial Pure Exploration with Bottleneck Reward Function »
Yihan Du · Yuko Kuroki · Wei Chen 
2021 Poster: The Hardness Analysis of Thompson Sampling for Combinatorial Semibandits with Greedy Oracle »
Fang Kong · Yueran Yang · Wei Chen · Shuai Li 
2020 Poster: Online Influence Maximization under Linear Threshold Model »
Shuai Li · Fang Kong · Kejie Tang · Qizhi Li · Wei Chen 
2020 Poster: Hedging in games: Faster convergence of external and swap regrets »
Xi Chen · Binghui Peng 
2020 Spotlight: Hedging in games: Faster convergence of external and swap regrets »
Xi Chen · Binghui Peng 
2018 Poster: Community Exploration: From Offline Optimization to Online Learning »
Xiaowei Chen · Weiran Huang · Wei Chen · John C. S. Lui 
2017 Poster: Improving Regret Bounds for Combinatorial SemiBandits with Probabilistically Triggered Arms and Its Applications »
Qinshi Wang · Wei Chen 
2017 Poster: Influence Maximization with $\varepsilon$Almost Submodular Threshold Functions »
Qiang Li · Wei Chen · Institute of Computing Xiaoming Sun · Institute of Computing Jialin Zhang 
2016 Poster: Combinatorial MultiArmed Bandit with General Reward Functions »
Wei Chen · Wei Hu · Fu Li · Jian Li · Yu Liu · Pinyan Lu 
2015 Poster: Stochastic Online Greedy Learning with Semibandit Feedbacks »
Tian Lin · Jian Li · Wei Chen 
2014 Poster: Combinatorial Pure Exploration of MultiArmed Bandits »
Shouyuan Chen · Tian Lin · Irwin King · Michael R Lyu · Wei Chen 
2014 Oral: Combinatorial Pure Exploration of MultiArmed Bandits »
Shouyuan Chen · Tian Lin · Irwin King · Michael R Lyu · Wei Chen