Institute of Information Science, Academia Sinica

Events

Print

Press Ctrl+P to print from browser

A $(1-1/e)^2$-Approximation for Adaptive Seeding with Monotone Submodular Functions

:::

A $(1-1/e)^2$-Approximation for Adaptive Seeding with Monotone Submodular Functions

  • LecturerMr. Lior Seeman (Department of Computer Science, Cornell University)
    Host: Kai-Min Chung
  • Time2014-12-19 (Fri.) 15:00 ~ 16:00
  • LocationAuditorium 126 at CITI Building
Abstract

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.

BIO

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.