# Submodular Maximization in Clean Linear Time

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jun 2020.

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

- [Data-Efficient Structured Pruning via Submodular Optimization](https://mlsanity.com/paper/2203.04940/) (2022)
- [A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback](https://mlsanity.com/paper/2301.13326/) (2023)
- [Active Learning in Bayesian Neural Networks with Balanced Entropy Learning Principle](https://mlsanity.com/paper/2105.14559/) (2021)
- [Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint](https://mlsanity.com/paper/2305.10292/) (2023)
- [Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraint](https://mlsanity.com/paper/2405.13994/) (2024)
- [Submodular Maximization under the Intersection of Matroid and Knapsack Constraints](https://mlsanity.com/paper/2307.09487/) (2023)
- [Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity](https://mlsanity.com/paper/2405.12252/) (2024)
- [A Note On Deterministic Submodular Maximization With Bounded Curvature](https://mlsanity.com/paper/2409.02943/) (2024)
- [Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint](https://mlsanity.com/paper/2409.04415/) (2024)
- [Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint](https://mlsanity.com/paper/2511.02254/) (2025)

## Abstract (arXiv)

In this paper, we provide the first deterministic algorithm that achieves the tight 1-1/e approximation guarantee for submodular maximization under a cardinality (size) constraint while making a number of queries that scales only linearly with the size of the ground set n. To complement our result, we also show strong information-theoretic lower bounds. More specifically, we show that when the maximum cardinality allowed for a solution is constant, no algorithm making a sub-linear number of function evaluations can guarantee any constant approximation ratio. Furthermore, when the constraint allows the selection of a constant fraction of the ground set, we show that any algorithm making fewer than Omega(n/log(n)) function evaluations cannot perform better than an algorithm that simply outputs a uniformly random subset of the ground set of the right size. We then provide a variant of our deterministic algorithm for the more general knapsack constraint, which is the first linear-time algorithm that achieves 1/2-approximation guarantee for this constraint. Finally, we extend our results to the general case of maximizing a monotone submodular function subject to the intersection of a p-set system and multiple knapsack constraints. We extensively evaluate the performance of our algorithms on multiple real-life machine learning applications, including movie recommendation, location summarization, twitter text summarization and video summarization.