Treffer: 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. 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 (½ + ε)-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 v = k/k - 1 such that any algorithm achieving a better than (1 - 1/v) = 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 - 1/v - o(1))-approximation algorithm assuming fractional base packing number at least v, where v ∈ (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 ¼ - ε. For this problem, we obtain a hardness of (½ + ε)-approximation for any fixed ε > 0. [ABSTRACT FROM AUTHOR]

Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)