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.