Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
This paper studies an adaptive version of the heavily studied influence maximization problem. The problem is the adaptive influence maximization problem with myopic feedback in the independent cascade model. In the adaptive influence maximization problem, the seed nodes are sequentially selected one by one. After each seed selection, some information (feedback) about the spread of influence is returned to the algorithm which could be used for the selection of the next seeds. In the myopic feedback, the set of activated immediate neighbors of the selected seed is returned as such feedback. Finally, in the independent cascade model, every edge of the graph has an independent probability of passing the influence. This problem was first formally considered by Golovin and Krause a decade ago. This problem was studied in the context of the adaptive submodularity framework. In this line of work one seeks objectives that are adaptive submodular which can then be optimized within a constant factor using a simple greedy algorithm. The main challenge with the model studied in this paper is that it is not adaptive submodular. It was an open problem if a constant approximation can be achieved. The paper gives a (1-1/e)/4-approximation algorithm for this problem as well as a lower bound.