Back to Search
Start Over
Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
- Source :
- SIAM Journal on Computing. 43:1831-1879
- Publication Year :
- 2014
- Publisher :
- Society for Industrial & Applied Mathematics (SIAM), 2014.
-
Abstract
- We consider the problem of maximizing a nonnegative submodular set function $f:2^N \rightarrow {\mathbb R}_+$ over a ground set $N$ subject to a variety of packing-type constraints including (multiple) matroid constraints, knapsack constraints, and their intersections. In this paper we develop a general framework that allows us to derive a number of new results, in particular, when $f$ may be a nonmonotone function. Our algorithms are based on (approximately) maximizing the multilinear extension $F$ of $f$ over a polytope $P$ that represents the constraints, and then effectively rounding the fractional solution. Although this approach has been used quite successfully, it has been limited in some important ways. We overcome these limitations as follows. First, we give constant factor approximation algorithms to maximize $F$ over a downward-closed polytope $P$ described by an efficient separation oracle. Previously this was known only for monotone functions. For nonmonotone functions, a constant factor was ...
Details
- ISSN :
- 10957111 and 00975397
- Volume :
- 43
- Database :
- OpenAIRE
- Journal :
- SIAM Journal on Computing
- Accession number :
- edsair.doi...........e83e35229032811c0b30385aeb2037de