# Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint

arXiv: https://arxiv.org/abs/2408.03583 · HTML: https://mlsanity.com/paper/2408.03583/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Aug 2024.

## Built on by (most cited first, 6 of 6)

- [The Cost of Consistency: Submodular Maximization with Constant Recourse](https://mlsanity.com/paper/2412.02492/) (2024)
- [A Note On Deterministic Submodular Maximization With Bounded Curvature](https://mlsanity.com/paper/2409.02943/) (2024)
- [Allocating Variance to Maximize Expectation](https://mlsanity.com/paper/2502.18463/) (2025)
- [Matroid Algorithms Under Size-Sensitive Independence Oracles](https://mlsanity.com/paper/2605.00201/) (2026)
- [Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids, and Full-Bandit Learning](https://mlsanity.com/paper/2608.12134/) (2026)
- [Bandit Submodular Maximization under Matroid Constraints: Learning Compressed Exchange Policy](https://mlsanity.com/paper/2608.24627/) (2026)

## Abstract (arXiv)

We study the problem of maximizing a monotone submodular function subject to a matroid constraint, and present for it a deterministic non-oblivious local search algorithm that has an approximation guarantee of 1 - 1/e - varepsilon (for any varepsilon > 0) and query complexity of tildeO_varepsilon(nr), where n is the size of the ground set and r is the rank of the matroid. Our algorithm vastly improves over the previous state-of-the-art 0.5008-approximation deterministic algorithm, and in fact, shows that there is no separation between the approximation guarantees that can be obtained by deterministic and randomized algorithms for the problem considered. The query complexity of our algorithm can be improved to tildeO_varepsilon(n + r√n) using randomization, which is nearly-linear for r = O(√n), and is always at least as good as the previous state-of-the-art algorithms.