Title: Submodular Optimization: Maximization, Learning, and Applications 

Speaker: Vahab Mirrokni, Google-NYC 
 
Optimizing submodular functions in a central problem in combinatorial optimization with several applications.
 I will present the first constant-factor approximation algorithms for maximizing non-monotone submodular 
functions. In particular, we give a deterministic local search 1/3-approximation and a randomized 2/5-
approximation algorithm for maximizing non-negative submodular functions. Furthermore, we prove that achieving
 an approximation factor better than 1/2 requires  exponential time. Finally, I will  describe a tight $O
(\sqrt{n})$-approximation algorithm for learning a submodular function with polynomial number of queries.



If there is enough interest, I will discuss applications of submodular maximization in the growing field of 
the online advertisement, and in particular in marketing over social networks.



The talk surveys joint work with Feige, Vondrak (FOCS'07), Hartline, Sundararajan (WWW'07), Feige, Immorlica,
 Nazerzade (submitted), and Goemans, Iwata, and Harvey (submitted).