Maximizing Non-monotone Submodular Functions under Matroid and Knapsack Constraints

Jon Lee (jonleeus.ibm.com)
Vahab S. Mirrokni (mirroknigoogle.com)
Viswanath Nagarajan (viswanatandrew.cmu.edu)
Maxim Sviridenko (svirius.ibm.com)

Abstract: 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 $\left({1\over k+2+{1\over k}+\epsilon}\right)$-approximation for the submodular maximization problem under $k$ matroid constraints, and a $\left({1\over 5}-\epsilon\right)$-approximation algorithm for this problem subject to $k$ knapsack constraints ($\epsilon>0$ is any constant). We improve the approximation guarantee of our algorithm to ${1\over k+1+{1\over k-1}+\epsilon}$ for $k\ge 2$ partition matroid constraints. This idea also gives a $\left({1\over k+\epsilon}\right)$-approximation for maximizing a monotone submodular function subject to $k\ge 2$ partition matroids, which improves over the previously best known guarantee of $\frac{1}{k+1}$.

Keywords: submodular maximization, matroid, knapsack, approximation algorithm

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Approximation Algorithms )

Category 3: Combinatorial Optimization (Graphs and Matroids )

Citation: IBM Research Report RC24679

Download: [PDF]

Entry Submitted: 10/24/2008
Entry Accepted: 10/25/2008
Entry Last Modified: 10/27/2008

Modify/Update this entry