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 discuss applications of submodular maximization in the problem of marketing digital goods on social networks, and revenue maximization for banner advertisement.
Main body of the talk is joint work with Uri Feige and Jan Vondrak.
(The Algorithms
and Complexity Seminar series talks are usually held Thursdays from
4-5:15pm in 32-G575.)