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).