We consider the monotone submodular k-set packing problem in the context of the more general problem of maximizing a monotone submodular function in a k-exchange system. These systems, introduced by [Feldman,2011], generalize the matroid k-parity problem in a wide class of matroids and capture many other combinatorial optimization problems. We give a deterministic, non-oblivious local search algorithm that attains an approximation ratio of (k + 3) 2 + epsilon for the problem of maximizing a monotone submodular function in a k-exchange system, improving on the best known result of k+epsilon, and answering an open question posed by
Consider a suboptimal solution S for a maximization problem. Suppose S's value is small compared to an optimal solution OPT to the problem, yet S is structurally similar to OPT. A natural question in this setting is whether there is a way of improving S based solely on this information. In this paper we introduce the Structural Continuous Greedy Algorithm, answering this question affirmatively in the setting of the Nonmonotone Submodular Maximization Problem. We improve on the best approximation factor known for this problem. In the Nonmonotone Submodular Maximization Problem we are given a non-negative submodular function f, and the objective is to find a subset maximizing f. Our method yields an 0.42-approximation for this problem, improving on the current best approximation factor of 0.41 given by Gharan and Vondrak [5]. On the other hand, [4] showed a lower bound of 0.5 for this problem. Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. In this paper, we give the first constant-factor approximation algorithm for maximizing any non-negative submodular function subject to multiple matroid or knapsack constraints. We emphasize that our results are for non-monotone submodular functions. In particular, for any constant k, we present a (1 k+2+1 k+e)-approximation for the submodular maximization problem under k matroid constraints, and a (1 5-e)-approximation algorithm for this problem subject to k knapsack constraints (e>0 is any constant). We improve the approximation guarantee of our algorithm to 1 k+1+ 1 k-1 +e for k≥2 partition matroid constraints. This idea also gives a ( 1 k+e)-approximation for maximizing a monotone submodular function subject to k≥2 partition matroids, which improves over the previously best known guarantee of 1 k+1. Submodular maximization generalizes many important problems including Max Cut in directed undirected graphs and hypergraphs, certain constraint satisfaction problems and maximum facility location problems. Unlike the problem of minimizing submodular functions, the problem of maximizing submodular functions is NP-hard. Submodular maximization and set systems play a major role in combinatorial optimization. It is long known that the greedy algorithm provides a 1 (k + 1)-approximation for maximizing a monotone submodular function over a k-system. For the special case of k-matroid intersection, a local search approach was recently shown to provide an improved approximation of 1 (k +δ) for arbitrary δ > 0. Unfortunately, many fundamental optimization problems are represented by a k-system which is not a k-intersection. An interesting question is whether the local search approach can be extended to include such problems. We answer this question affirmatively. Motivated by the b-matching and k-set packing problems, as well as the more general matroid k-parity problem, we introduce a new class of set systems called k-exchange systems, that includes k-set packing, b-matching, matroid k-parity in strongly base orderable matroids, and additional combinatorial optimization problems such as: independent set in (k+1)-claw free graphs, asymmetric TSP, job interval selection with identical lengths and frequency allocation on lines. We give a natural local search algorithm which improves upon the current greedy approximation, for this new class of independence systems. Unlike known local search algorithms for similar problems, we use counting arguments to bound the performance of our algorithm. Moreover, we consider additional objective functions and provide improved approximations for them as well. In the case of linear objective functions, we give a non-oblivious local search algorithm, that improves upon existing local search approaches for matroid k-parity. We consider the problem of maximizing a nonnegative (possibly non-monotone) submodular set function with or without constraints. [9] showed a 2 5-approximation for the unconstrained problem and also proved that no approximation better than 1 2 is possible in the value oracle model. Constant-factor approximation has been also known for submodular maximization subject to a matroid independence constraint (a factor of 0.309 [33]) and for submodular maximization subject to a matroid base constraint, provided that the fractional base packing number ν is bounded away from 1 (a 1 4-approximation assuming that ν ≥ 2 [33]). In this paper, we propose a new algorithm for submodular maximization which is based on the idea of simulated annealing. We prove that this algorithm achieves improved approximation for two problems: a 0.41-approximation for unconstrained submodular maximization, and a 0.325-approximation for submodular maximization subject to a matroid independence constraint. On the hardness side, we show that in the value oracle model it is impossible to achieve a 0.478-approximation for submodular maximization subject to a matroid independence constraint, or a 0.394-approximation subject to a matroid base constraint in matroids with two disjoint bases. Even for the special case of cardinality constraint, we prove it is impossible to achieve a 0.491-approximation. (Previously it was conceivable that a 1 2-approximation exists for these problems.) It is still an open question whether a 1 2-approximation is possible for unconstrained submodular maximization. Submodular function maximization is a central problem in combinatorial optimization, generalizing many important NP-hard problems including max cut in digraphs, graphs, and hypergraphs; certain constraint satisfaction problems; maximum entropy sampling; and maximum facility location problems. Our main result is that for any k ≥ 2 and any e > 0, there is a natural local search algorithm that has approximation guarantee of 1 (k + e) for the problem of maximizing a monotone submodular function subject to k matroid constraints. This improves upon the 1 (k + 1)-approximation of Fisher, Nemhauser, and Wolsey obtained in 1978 [Fisher, M., G. Nemhauser, L. Wolsey. 1978. An analysis of approximations for maximizing submodular set functions---II. Math. Programming Stud.8 73--87]. Also, our analysis can be applied to the problem of maximizing a linear objective function and even a general nonmonotone submodular function subject to k matroid constraints. We show that, in these cases, the approximation guarantees of our algorithms are 1 (k-1 + e) and 1 (k + 1 + 1 (k-1) + e), respectively. Our analyses are based on two new exchange properties for matroids. One is a generalization of the classical Rota exchange property for matroid bases, and another is an exchange property for two matroids based on the structure of matroid intersection.