About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
FOCS 2009
Conference paper
Symmetry and approximability of submodular maximization problems
Abstract
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.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 v = k/k-1, such that any algorithm achieving a better than (1-1/v)-approximation for this class would require exponentially many value queries. On the positive side, we present a 1/2(1-1/v-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/v (for a matroid base constraint) can be achieved algorithmically and hence are optimal. © 2009 IEEE.