# Greed is Good: Near-Optimal Submodular Maximization via Greedy Optimization

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Apr 2017.

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

- [Learning Interpretable Decision Rule Sets: A Submodular Optimization Approach](https://mlsanity.com/paper/2206.03718/) (2022)
- [Generating Diverse and High-Quality Texts by Minimum Bayes Risk Decoding](https://mlsanity.com/paper/2401.05054/) (2024)
- [Optimal Sampling Gaps for Adaptive Submodular Maximization](https://mlsanity.com/paper/2104.01750/) (2021)
- [Using Partial Monotonicity in Submodular Maximization](https://mlsanity.com/paper/2202.03051/) (2022)
- [Learning Group Importance using the Differentiable Hypergeometric Distribution](https://mlsanity.com/paper/2203.01629/) (2022)
- [Fast Feature Selection with Fairness Constraints](https://mlsanity.com/paper/2202.13718/) (2022)
- [Optimizing Plastic Waste Collection in Water Bodies Using Heterogeneous Autonomous Surface Vehicles with Deep Reinforcement Learning](https://mlsanity.com/paper/2412.02316/) (2024)
- [Adaptive Sampling for Fast Constrained Maximization of Submodular Function](https://mlsanity.com/paper/2102.06486/) (2021)
- [The Power of Subsampling in Submodular Maximization](https://mlsanity.com/paper/2104.02772/) (2021)
- [Submodular Maximization under the Intersection of Matroid and Knapsack Constraints](https://mlsanity.com/paper/2307.09487/) (2023)
- [Practical Parallel Algorithms for Non-Monotone Submodular Maximization](https://mlsanity.com/paper/2308.10656/) (2023)

## Abstract (arXiv)

It is known that greedy methods perform well for maximizing monotone submodular functions. At the same time, such methods perform poorly in the face of non-monotonicity. In this paper, we show - arguably, surprisingly - that invoking the classical greedy algorithm O(√k)-times leads to the (currently) fastest deterministic algorithm, called Repeated Greedy, for maximizing a general submodular function subject to k-independent system constraints. Repeated Greedy achieves (1 + O(1/√k))k approximation using O(nr√k) function evaluations (here, n and r denote the size of the ground set and the maximum size of a feasible solution, respectively). We then show that by a careful sampling procedure, we can run the greedy algorithm only once and obtain the (currently) fastest randomized algorithm, called Sample Greedy, for maximizing a submodular function subject to k-extendible system constraints (a subclass of k-independent system constrains). Sample Greedy achieves (k + 3)-approximation with only O(nr/k) function evaluations. Finally, we derive an almost matching lower bound, and show that no polynomial time algorithm can have an approximation ratio smaller than  k + 1/2 - varepsilon. To further support our theoretical results, we compare the performance of Repeated Greedy and Sample Greedy with prior art in a concrete application (movie recommendation). We consistently observe that while Sample Greedy achieves practically the same utility as the best baseline, it performs at least two orders of magnitude faster.