Submodular Maximization over a Matroid $k$-Intersection: Multiplicative Improvement over Greedy

Moran Feldman, Justin Ward

We study the problem of maximizing a non-negative monotone submodular objective $f$ subject to the intersection of $k$ arbitrary matroid constraints. The natural greedy algorithm g…