×

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.)
PDF BibTeX XML Cite
Full Text: DOI