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

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 guarantees (k + 1)-approximation for this problem, and the state-of-the-art algorithm only improves this approximation ratio to k. We give a (Formula presented) approximation algorithm for this problem. Our result is the first multiplicative improvement over the approximation ratio of the greedy algorithm for general k. We further show that our algorithm can be used to obtain roughly the same approximation ratio also for the more general problem in which the objective is not guaranteed to be monotone (the sublinear term in the approximation ratio becomes O(k²/³) rather than O(^√k) in this case). All of our results hold also when the k-matroid intersection constraint is replaced with a more general matroid k-parity constraint. Furthermore, unlike the case in many of the previous works, our algorithms run in time that is independent of k and polynomial in the size of the ground set. Our algorithms are based on a hybrid greedy local search approach recently introduced by Singer and Thiery [38] for the weighted matroid k-intersection problem, which is a special case of the problem we consider. Leveraging their approach in the submodular setting requires several non-trivial insights and algorithmic modifications since the marginals of a submodular function f, which correspond to the weights in the weighted case, are not independent of the algorithm's internal randomness. In the special weighted case studied by [38], our algorithms reduce to a variant of the algorithm of [38] with an improved approximation ratio of (k + 1) ln 2 + O(ε) < 0.694k + 0.694 + O(ε), compared to an approximation ratio of (Formula presented) guaranteed by Singer and Thiery [38].