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. These results hold typically in the value oracle model, where the objective function is accessible via a black box returning f(S) for a given S. 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 and the impossibility of ( 1/2 +ε)-approximation for unconstrained (nonmonotone) submodular maximization. As a new application, we consider the problem of maximizing a nonmonotone 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. 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/ν) = 1 k -approximation for this class would require exponentially many value queries. In particular, there is no constant factor approximation for maximizing a nonmonotone submodular function over the bases of a general matroid. On the positive side, we present a 1 2 (1- 1/ν -o(1))-approximation algorithm assuming fractional base packing number at least ν, where ν ε (1, 2]. We also present an improved 0.309-approximation for maximization of a nonmonotone submodular function subject to a matroid independence constraint, improving the previously known factor of 1/4 -ε. For this problem, we obtain a hardness of ( 1/2 +ε)-approximation for any fixed ε > 0. © 2013 Society for Industrial and Applied Mathematics.