Maximizing a monotone submodular function subject to a matroid constraint

Abstract

Let f: 2 X → R + be a monotone submodular set function, and let (X, I) be a matroid. We consider the problem max s∈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|≤kf (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. © 2011 Society for Industrial and Applied Mathematics.