Lee, Jon, Mirrokni, Vahab S., Nagarajan, Viswanath and Sviridenko, Maxim (2009) Non-monotone submodular maximization under matroid and knapsack constraints. In: 41st ACM Symposium on Theory of Computing (STOC 2009), Bethesda, Maryland, 31 May - 2 Jun 2009. Published in: STOC '09 Proceedings of the 41st annual ACM symposium on Theory of computing p. 323.

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 (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.

Request changes to a record

Actions (login required)

View Item