# Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity

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

## Key facts

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

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

- [Parallelizing Thompson Sampling](https://mlsanity.com/paper/2106.01420/) (2021)
- [Sequential Attention for Feature Selection](https://mlsanity.com/paper/2209.14881/) (2022)
- [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)
- [Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models](https://mlsanity.com/paper/2206.09563/) (2022)
- [Practical Parallel Algorithms for Non-Monotone Submodular Maximization](https://mlsanity.com/paper/2308.10656/) (2023)
- [GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility](https://mlsanity.com/paper/2405.18754/) (2024)
- [Sample-Adaptivity Tradeoff in On-Demand Sampling](https://mlsanity.com/paper/2511.15507/) (2025)
- [Greedy PIG: Adaptive Integrated Gradients](https://mlsanity.com/paper/2311.06192/) (2023)
- [Accelerated Relax-and-Round for Concave Coverage Problems](https://mlsanity.com/paper/2605.06900/) (2026)
- [Minibatch Selection for Language Models via Partition Matroid Constrained Gradient Matching](https://mlsanity.com/paper/2606.07954/) (2026)

## Abstract (arXiv)

Submodular optimization generalizes many classic problems in combinatorial optimization and has recently found a wide range of applications in machine learning (e.g., feature engineering and active learning). For many large-scale optimization problems, we are often concerned with the adaptivity complexity of an algorithm, which quantifies the number of sequential rounds where polynomially-many independent function evaluations can be executed in parallel. While low adaptivity is ideal, it is not sufficient for a distributed algorithm to be efficient, since in many practical applications of submodular optimization the number of function evaluations becomes prohibitively expensive. Motivated by these applications, we study the adaptivity and query complexity of adaptive submodular optimization. Our main result is a distributed algorithm for maximizing a monotone submodular function with cardinality constraint k that achieves a (1-1/e-varepsilon)-approximation in expectation. This algorithm runs in O(log(n)) adaptive rounds and makes O(n) calls to the function evaluation oracle in expectation. The approximation guarantee and query complexity are optimal, and the adaptivity is nearly optimal. Moreover, the number of queries is substantially less than in previous works. Last, we extend our results to the submodular cover problem to demonstrate the generality of our algorithm and techniques.