## 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∈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 = 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.

Original language | English (US) |
---|---|

Pages (from-to) | 1740-1766 |

Number of pages | 27 |

Journal | SIAM Journal on Computing |

Volume | 40 |

Issue number | 6 |

DOIs | |

State | Published - 2011 |

## Keywords

- Approximation algorithm
- Generalized assignment problem
- Matroid
- Monotone submodular set function
- Social welfare

## ASJC Scopus subject areas

- General Computer Science
- General Mathematics