# An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Nov 2018.

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

- [Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity](https://mlsanity.com/paper/2102.08327/) (2021)
- [On the Complexity of Dynamic Submodular Maximization](https://mlsanity.com/paper/2111.03198/) (2021)
- [Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel](https://mlsanity.com/paper/2111.07917/) (2021)
- [Fast Feature Selection with Fairness Constraints](https://mlsanity.com/paper/2202.13718/) (2022)
- [Adaptive Sampling for Fast Constrained Maximization of Submodular Function](https://mlsanity.com/paper/2102.06486/) (2021)
- [Practical Parallel Algorithms for Non-Monotone Submodular Maximization](https://mlsanity.com/paper/2308.10656/) (2023)
- [E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time](https://mlsanity.com/paper/2506.07747/) (2025)
- [Sample-Adaptivity Tradeoff in On-Demand Sampling](https://mlsanity.com/paper/2511.15507/) (2025)

## Abstract (arXiv)

In this paper we study submodular maximization under a matroid constraint in the adaptive complexity model. This model was recently introduced in the context of submodular optimization in [BS18a] to quantify the information theoretic complexity of black-box optimization in a parallel computation model. Informally, the adaptivity of an algorithm is the number of sequential rounds it makes when each round can execute polynomially-many function evaluations in parallel. Since submodular optimization is regularly applied on large datasets we seek algorithms with low adaptivity to enable speedups via parallelization. Consequently, a recent line of work has been devoted to designing constant factor approximation algorithms for maximizing submodular functions under various constraints in the adaptive complexity model [BS18a, BS18b, BBS18, BRS19, EN19, FMZ19, CQ19, ENV18, FMZ18]. Despite the burst in work on submodular maximization in the adaptive complexity model the fundamental problem of maximizing a monotone submodular function under a matroid constraint has remained elusive. In particular, all known techniques fail for this problem and there are no known constant factor approximation algorithms whose adaptivity is sublinear in the rank of the matroid k or in the worst case sublinear in the size of the ground set n. In this paper we present an approximation algorithm for the problem of maximizing a monotone submodular function under a matroid constraint in the adaptive complexity model. The approximation guarantee of the algorithm is arbitrarily close to the optimal 1-1/e and it has near optimal adaptivity of O(log(n)log(k)). This result is obtained using a novel technique of adaptive sequencing which departs from previous techniques for submodular maximization in the adaptive complexity model.