Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
Authors:
- Jon LeeJLJon Lee
- Vahab S. MirrokniVMVahab S. Mirrokni
- Viswanath NagarajanVNViswanath Nagarajan
- Maxim SviridenkoMSMaxim Sviridenko
- 1 January 2010
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 23 (4) , 2053-2078
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 nonnegative submodular function subject to multiple matroid or knapsack constraints. We emphasize that our results are for nonmonotone submodular functions. In particular, for any constant k, we present a $(\frac{1}{k+2+\frac{1}{k}+\epsilon})$-approximation for the submodular maximization problem under k matroid constraints, and a $(\frac{1}{5}-\epsilon)$-approximation algorithm for this problem subject to k knapsack constraints ($\epsilon>0$ is any constant). We improve the approximation guarantee of our algorithm to $\frac{1}{k+1+\frac{1}{k-1}+\epsilon}$ for $k\geq2$ partition matroid constraints. This idea also gives a $(\frac{1}{k+\epsilon})$-approximation for maximizing a monotone submodular function subject to $k\geq2$ partition matroids, which is an improvement over the previously best known guarantee of $\frac{1}{k+1}$.
Keywords
All Related Versions
This publication has 40 references indexed in Scilit:
- Solving maximum-entropy sampling problems using factored masksMathematical Programming, 2006
- Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance GuaranteeJournal of Combinatorial Optimization, 2004
- A 0.5-Approximation Algorithm for MAX DICUT with Given Sizes of PartsSIAM Journal on Discrete Mathematics, 2001
- An 0.828-approximation algorithm for the uncapacitated facility location problemDiscrete Applied Mathematics, 1999
- Using continuous nonlinear relaxations to solve. constrained maximum-entropy sampling problemsMathematical Programming, 1999
- A threshold of ln n for approximating set coverJournal of the ACM, 1998
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- Canonical decompositions of symmetric submodular systemsDiscrete Applied Mathematics, 1983
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate AlgorithmsManagement Science, 1977
- On the Uncapacitated Location Problem1977