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].

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: DOI