# Submodular Optimization Problems and Greedy Strategies: A Survey

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 May 2019.

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

- [Nonlinear Bayesian optimal experimental design using logarithmic Sobolev inequalities](https://mlsanity.com/paper/2402.15053/) (2024)
- [Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models](https://mlsanity.com/paper/2206.09563/) (2022)
- [Joint Semantic Token Selection and Prompt Optimization for Interpretable Prompt Learning](https://mlsanity.com/paper/2605.04425/) (2026)

## Abstract (arXiv)

The greedy strategy is an approximation algorithm to solve optimization problems arising in decision making with multiple actions. How good is the greedy strategy compared to the optimal solution? In this survey, we mainly consider two classes of optimization problems where the objective function is submodular. The first is set submodular optimization, which is to choose a set of actions to optimize a set submodular objective function, and the second is string submodular optimization, which is to choose an ordered set of actions to optimize a string submodular function. Our emphasis here is on performance bounds for the greedy strategy in submodular optimization problems. Specifically, we review performance bounds for the greedy strategy, more general and improved bounds in terms of curvature, performance bounds for the batched greedy strategy, and performance bounds for Nash equilibria.