# A Note On Deterministic Submodular Maximization With Bounded Curvature

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 7 references that are in the map.
- First posted on arXiv 25 Aug 2024.

## Builds on (most cited first, 6 of 6)

- [Optimal approximation for submodular and supermodular optimization with bounded curvature](https://mlsanity.com/paper/1311.4728/) (2013)
- [Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications](https://mlsanity.com/paper/1904.09354/) (2019)
- [Deterministic Algorithms for Submodular Maximization Problems](https://mlsanity.com/paper/1508.02157/) (2015)
- [Submodular Maximization in Clean Linear Time](https://mlsanity.com/paper/2006.09327/) (2020)
- [Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint](https://mlsanity.com/paper/2408.03583/) (2024)
- [Deterministic (1/2 + ε)-Approximation for Submodular Maximization over a Matroid](https://mlsanity.com/paper/1807.05532/) (2018)

## Abstract (arXiv)

We show that the recent breakthrough result of [Buchbinder and Feldman, FOCS'24] could further lead to a deterministic (1-kappaf/e-varepsilon)-approximate algorithm for maximizing a submodular function with curvature kappaf under matroid constraint.