Maximizing a Monotone Submodular Function Subject to a Matroid Constraint

Let f: 2X R_+ be a monotone submodular set function, and let (X, I) be a matroid. We consider the problem maxₒ ₈ f (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|ₒ| ₊ 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) for 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.