Approximability of Adaptive Seeding under Knapsack Constraints
Aviad Rubinstein, Lior Seeman, Yaron Singer · 2015
Adapting Seeding is a key algorithmic challenge of influence maximization in social networks. One seeks to select among certain available nodes in a network, and then, adaptively, among neighbors of those nodes as they become available, in order to maximize influence in the overall network. Despite recent strong approximation results [Seeman and Singer 2013; Badanidiyuru et al. 2015], very little is known about the problem when nodes can take on different activation costs. Surprisingly, designing adaptive seeding algorithms that can appropriately incentivize users with heterogeneous activation costs introduces fundamental challenges that do not exist in the simplified version of the problem.