Mar 4, 2015

The Adaptive Seeding problem is a two-stage stochastic optimization framework initially motivated by maximizing influence 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 a global objective function. More generally, adaptive seeding is a stochastic optimization framework where the choices in the first stage affect the realizations of nature, over which we aim to optimize.

In this talk I present a $(1-1/e)^2$ -approximation for adaptive seeding of general monotone submodular functions. Our algorithm uses a new concept we call \emph{locally-adaptive} policies. This policies combine a global non-adaptive structure with local adaptive decisions. We show this policies have good adaptivity gap and allow for good approximations.

Joint work with with Ashwin Badanidiyuru, Christos Papadimitriou, Aviad Rubinstein and Yaron Singer.