# zbMATH — the first resource for mathematics

Maximizing a submodular set function subject to a matroid constraint (extended abstract). (English) Zbl 1136.90449
Fischetti, Matteo (ed.) et al., Integer programming and combinatorial optimization. 12th international IPCO conference, Ithaca, NY, USA, June 25–27, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-72791-0/pbk). Lecture Notes in Computer Science 4513, 182-196 (2007).
Let $$f$$: 2^N \rightarrow \cal R^+$$be a non-decreasing submodular set function, and let$$(N,\cal I)$$be a matroid. We consider the problem$$\max_S \in \cal I f(S)$$. It is known that the greedy algorithm yields a 1/2-approximation for this problem. It is also known, via a reduction from the max-$$k$$-cover problem, that there is no$$(1 - 1/e + \epsilon )$$-approximation for any constant$$\epsilon > 0$$, unless$$P = NP$$. In this paper, we improve the 1/2-approximation to a$$(1 - 1/e)$$-approximation, when$$f$$is a sum of weighted rank functions of matroids. This class of functions captures a number of interesting problems including set coverage type problems. Our main tools are the pipage rounding technique of {\mathit A. A. Ageev} and {\mathit M. I. Sviridenko} [Pipage rounding: a new method of constructing algorithms with proven performance guarantee", J. Comb. Optim. 8, No. 3, 307--328 (2004; Zbl 1084.90029)] and a probabilistic lemma on monotone submodular functions that might be of independent interest. We show that the generalized assignment problem (GAP) is a special case of our problem; although the reduction requires$$|N|$$to be exponential in the original problem size, we are able to interpret the recent$$(1 - 1/e)$$-approximation for GAP by {\mathit L. Fleischer}, {\mathit M. X. Goemans}, {\mathit V. S. Mirrokni} and {\mathit M. Sviridenko} [Tight approximation algorithms for maximum general assignment problems", in: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, 611--620 (2006)] in our framework. This enables us to obtain a$$(1 - 1/e)$$-approximation for variants of GAP with more complex constraints.$$
For the entire collection see [Zbl 1121.90003].

##### MSC:
 90C27 Combinatorial optimization 05B35 Combinatorial aspects of matroids and geometric lattices 52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)
Full Text: