Maximizing a monotone submodular function subject to a matroid constraint. (English) Zbl 1234.68459

Calinescu, Gruia; Chekuri, Chandra; Pál, Martin; Vondrák, Jan

SIAM J. Comput. 40, No. 6, 1740-1766 (2011).

MSC:

68W20	Randomized algorithms
68W25	Approximation algorithms
52B40	Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)

Keywords:

monotone submodular set function; matroid; social welfare; generalized assignment problem; approximation algorithm

Citations:

Zbl 0408.90085; Zbl 0395.90072; Zbl 1065.68573; Zbl 1084.90029; Zbl 1231.91094