Computer Science/Discrete Mathematics Seminar I

A number of recent results on optimization problems involving submodular functions have made use of the "multilinear relaxation" of the problem. I will show a general approach to deriving inapproximability results in the value oracle model, based on the notion of "symmetry gap". The main result says that for any fixed instance that exhibits a certain "symmetry gap" in its multilinear relaxation, there is a naturally related class of instances for which a better approximation factor than the symmetry gap is impossible. This unifies several known query complexity results for submodular maximization. As a new application, we consider the problem of maximizing a non-monotone submodular function over the bases of a matroid. We show that the best approximation one can achieve is related to the fractional base packing number of the matroid. For the class of matroids with fractional base packing number at least P, we show a (1-1/P)/2 - approximation algorithm, and our general result implies that this is optimal within a factor of 2.