Submodular Function Approximation

Combinatorics Seminar
Friday, August 21, 2009 - 15:00
1 hour (actually 50 minutes)
Skiles 255
Kyoto University
In this lecture, I will explain the greedy approximation algorithm on submodular function maximization due to Nemhauser, Wolsey, and Fisher. Then I will apply this algorithm to the problem of approximating an monotone submodular functions by another submodular function with succinct representation. This approximation method is based on the maximum volume ellipsoid inscribed in a centrally symmetric convex body. This is joint work with Michel Goemans, Nick Harvey, and Vahab Mirrokni.