Symmetry and approximability of submodular maximization problems

A number of recent results on optimization problems involving submodular functions have made use of the "multilinear relaxation" of the problem [3], [8], [24], [14], [13]. We present a general approach to deriving inapproximability results in the value oracle model, based on the notion of "symmetry gap". Our main result is 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 would require exponentially many oracle queries. This unifies several known hardness results for submodular maximization, e.g. the optimality of (1 - 1/epsilon)-approximation for monotone submodular maximization under a cardinality constraint [20], [7], and the impossibility of (1/2 + epsilon)-approximation for unconstrained (non-monotone) submodular maximization [8]. It follows from our result that (1/2 + epsilon)-approximation is also impossible for non-monotone submodular maximization subject to a (non-trivial) matroid constraint. On the algorithmic side, we present a 0.309-approximation for this problem, improving the previously known factor of 1/4 - o(1) [14]. As another application, we consider the problem of maximizing a non-monotone submodular function over the bases of a matroid. A (1/6 - o(1))-approximation has been developed for this problem, assuming that the matroid contains two disjoint bases [14]. We show that the best approximation one can achieve is indeed related to packings of bases in the matroid. Specifically, for any k >= 2, there is a class of matroids of fractional base packing number nu = k/k-1, such that any algorithm achieving a better than (1 - 1/nu)-approximation for this class would require exponentially many value queries. On the positive side, we present a 1/2 (1 - 1/nu - o(1))-approximation algorithm for the same problem. Our hardness results hold in fact for very special symmetric instances. For such symmetric instances, we show that the approximation factors of 1/2 (for submodular maximization subject to a matroid constraint) and 1 - 1/nu (for a matroid base constraint) can be achieved algorithmically and hence are optimal.