中央研究院 資訊科學研究所

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.

Our main result is a $(1-1/e)^2$-approximation for the adaptive seeding problem for any monotone submodular function. Often, adaptive policies are approximated via non-adaptive policies. For this class of problems we show a tight $1-1/e$ gap between optimal adaptive and non-adaptive policies, and a simple reduction implies no polynomial-time algorithm can obtain an approximation to the optimal non-adaptive solution better than $1-1/e$ unless P=NP. For some special cases, a non-adaptive approach can yield a $(1-1/e)^2$, but for general monotone submodular functions we show this approach fails. The main contribution in this paper is a novel method we develop based on a new concept we call [@BackSlash]emph{locally-adaptive} policies. This concept enables the $(1-1/e)^2$ -approximation for general monotone submodular functions and circumvents some of the impossibilities associated with non-adaptive policies. 

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

Lior Seeman is a fifth year PhD Student at the Computer Science Department of Cornell University.He is privileged to be advised by Joe Halpern and Rafael Pass. His research interests lie at the intersection of computer science, economics, social science, and cognitive science. He is interested in game theory, bounded rationality, cryptography, algorithms, social networks, and the interplay between them.