MAXIMIZING A MONOTONE SUBMODULAR FUNCTION SUBJECT TO A MATROID CONSTRAINT

Let f : 2(X) -> R+ be a monotone submodular set function, and let (X, I) be a matroid. We consider the problem max(S is an element of I)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(|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) 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 not equal 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. Vondrak, 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.