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/e)-approximation for monotone submodular maximization under a cardinality constraint [20], [7] , and the impossibility of ( 1 2 + )-approximation for unconstrained (non-monotone) submodular maximization [8] . It follows from our result that ( 1 2 + )-approximation is also impossible for non-monotone submodular maximization subject to a (non-trivial) matroid constraint. On the algorithmic side, we present a 0.309approximation 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 ν = k k−1 , such that any algorithm achieving a better than (1 − 1 ν )-approximation for this class would require exponentially many value queries. On the positive side, we present a 1 2 (1 − 1 ν − 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 ν (for a matroid base constraint) can be achieved algorithmically and hence are optimal.
The problem of maximizing a (not necessarily monotone) submodular function subject to a general matroid constraint was given a 0.309-approximation in Reference REF .
Symmetry and Approximability of Submodular Maximization Problems
2009 50th Annual IEEE Symposium on Foundations of Computer Science
2009 50th Annual IEEE Symposium on Foundations of Computer Science
Mathematics Computer Science