Submodular Maximization over a Matroid $k$-Intersection: Multiplicative Improvement over Greedy
Abstract
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 $\frac{2k\ln2}{1+\ln2}+O(\sqrt{k})
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Optimization and Search Problems
Game Theory and Voting Systems
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 9 February 2026
- Language
- EN
- Document type
- Preprint