Non-monotone submodular maximization under matroid and knapsack constraints

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. For the problem of maximizing a non-monotone submodular function, Feige, Mirrokni, and Vondrák recently developed a 2 5-approximation algorithm {FMV07}, however, their algorithms do not handle side constraints.} 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+ε)-approximation for the submodular maximization problem under k matroid constraints, and a (1 5-ε)-approximation algorithm for this problem subject to k knapsack constraints ($ε>0$ is any constant). We improve the approximation guarantee of our algorithm to 1 k+1+1 k-1+ε for k≥ 2 partition matroid constraints. This idea also gives a (1 k+ε)-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.