Back to Search
Start Over
MAXIMIZING A MONOTONE SUBMODULAR FUNCTION SUBJECT TO A MATROID CONSTRAINT.
- Source :
-
SIAM Journal on Computing . 2011, Vol. 40 Issue 6, p1740-1766. 27p. - Publication Year :
- 2011
-
Abstract
- Let f : 2X→R+ be a monotone submodular set function, and let (X, L)be a matroid. We consider the problem maxSεIf(S). It is known that the greedy algorithm yields a 1/2-approximation [M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey, Math. Programming Stud., no. 8 (1978), pp. 73-87] for this problem. For certain special cases, e.g., max|s|≤k f(S), the greedy algorithm yields a (1-1/e)-approximation. It is known that this is optimal both in the value oracle model (where the only access to f is through a black box returning f(S)f or a given set S) [G. L. Nemhauser and L. A. Wolsey, Math. Oper. Res., 3 (1978), pp. 177-188] and for explicitly posed instances assuming P ≠ NP [U. Feige, J. ACM, 45 (1998), pp. 634-652]. In this paper, we provide a randomized (1 - 1/e)-approximation for any monotone submodular function and an arbitrary matroid. The algorithm works in the value oracle model. Our main tools are a variant of the pipage rounding technique of Ageev and Sviridenko [J. Combin. Optim., 8 (2004), pp. 307-328], and a continuous greedy process that may be of independent interest. As a special case, our algorithm implies an optimal approximation for the submodular welfare problem in the value oracle model [J. Vondrák, Proceedings of the 38th ACM Symposium on Theory of Computing, 2008, pp. 67-74]. As a second application, we show that the generalized assignment problem (GAP) is also a special case; although the reduction requires |X| to be exponential in the original problem size, we are able to achieve a (1 -1/e - o(1))-approximation for GAP, simplifying previously known algorithms. Additionally, the reduction enables us to obtain approximation algorithms for variants of GAP with more general constraints. [ABSTRACT FROM AUTHOR]
- Subjects :
- *MATROIDS
*COMBINATORICS
*GRAPH theory
*SUBMODULAR functions
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 40
- Issue :
- 6
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 71607608
- Full Text :
- https://doi.org/10.1137/080733991