TIME: 1:30-2:20 pm, November 13, 2007 PLACE: CSE 503 SPEAKER: Vahab Mirrokni Microsoft Research TITLE: Maximizing non-monotone submodular functions ABSTRACT: Submodular maximization is a central problem in combinatorial optimization, generalizing Max-cut problems, and maximum facility location problems. Unlike the problem of minimizing submodular functions, the problem of maximizing submodular functions is NP-hard. We design the first constant-factor approximation algorithms for maximizing nonnegative submodular functions. In particular, we give a deterministic local search 1/3-approximation and a randomized 2/5-approximation algorithm for maximizing nonnegative submodular functions. We show that these algorithms give a 1/2-approximation for maximizing symmetric submdular functions. Furthermore, we prove that our 1/2-approximation for symmetric submodular functions is the best one can achieve with a subexponential number of value queries. Finally, I will mention recent results for learning submodular functions. As one application of our algorithm, I will also discuss a new application of this problem in marketing digital goods on social networks. The main part of the talk is joint work with Uri Feige and Jan Vondrak.