The Library
Non-monotone submodular maximization under matroid and knapsack constraints
Tools
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. doi:10.1145/1536414.1536459 ISSN 978-1-60558-506-2.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1145/1536414.1536459
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.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | STOC '09 Proceedings of the 41st annual ACM symposium on Theory of computing | ||||
Publisher: | ACM | ||||
ISSN: | 978-1-60558-506-2 | ||||
Book Title: | Proceedings of the 41st annual ACM symposium on Symposium on theory of computing - STOC '09 | ||||
Official Date: | 2009 | ||||
Dates: |
|
||||
Page Range: | p. 323 | ||||
DOI: | 10.1145/1536414.1536459 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 41st ACM Symposium on Theory of Computing (STOC 2009) | ||||
Type of Event: | Other | ||||
Location of Event: | Bethesda, Maryland | ||||
Date(s) of Event: | 31 May - 2 Jun 2009 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |