Maximizing Non-monotone Submodular Functions under Matroid and Knapsack Constraints

Copyright © [2010] by The Society for Industrial and Applied Mathematics. All rights reserved

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 -approximation for the submodular maximization problem under k matroid constraints, and a -approximation algorithm for this problem subject to k knapsack constraints ( is any constant). We improve the approximation guarantee of our algorithm to for partition matroid constraints. This idea also gives -approximation for maximizing a monotone submodular function subject to partition matroids, which improves over the previously best known guarantee of

By: Jon Lee; Vahab S. Mirrokni; Viswanath Nagarajan; Maxim Sviridenko

Published in: , volume 23, (no 4), pages 2053-78 in 2010

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .