# Constrained Submodular Maximization via New Bounds for DR-Submodular Functions

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Nov 2023.

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

- [G"odel Test: Can Large Language Models Solve Easy Conjectures?](https://mlsanity.com/paper/2509.18383/) (2025)
- [Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraint](https://mlsanity.com/paper/2405.13994/) (2024)
- [Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets](https://mlsanity.com/paper/2602.20578/) (2026)
- [Fairness in Submodular Maximization over a Matroid Constraint](https://mlsanity.com/paper/2312.14299/) (2023)
- [Bridging the Gap Between General and Down-Closed Convex Sets in Submodular Maximization](https://mlsanity.com/paper/2401.09251/) (2024)
- [GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility](https://mlsanity.com/paper/2405.18754/) (2024)
- [A Unified Approach to Submodular Maximization Under Noise](https://mlsanity.com/paper/2510.21128/) (2025)
- [Sparse by Rule: Probability-Based N:M Pruning for Spiking Neural Networks](https://mlsanity.com/paper/2511.12097/) (2025)
- [Stronger Approximation Guarantees for Non-Monotone γ-Weakly DR-Submodular Maximization](https://mlsanity.com/paper/2601.00611/) (2026)
- [Online Non-Monotone DR-Submodular Maximization Matching the Offline 0.401 Factor](https://mlsanity.com/paper/2609.02145/) (2026)
- [Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit](https://mlsanity.com/paper/2410.08578/) (2024)
- [Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint](https://mlsanity.com/paper/2511.02254/) (2025)
- [Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions](https://mlsanity.com/paper/2605.07902/) (2026)
- [Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering](https://mlsanity.com/paper/2609.15539/) (2026)
- [Approximating Optimal Policies in Heterogeneous Asynchronous Multi-player Bandits](https://mlsanity.com/paper/2610.18514/) (2026)

## Abstract (arXiv)

Submodular maximization under various constraints is a fundamental problem studied continuously, in both computer science and operations research, since the late 1970's. A central technique in this field is to approximately optimize the multilinear extension of the submodular objective, and then round the solution. The use of this technique requires a solver able to approximately maximize multilinear extensions. Following a long line of work, Buchbinder and Feldman (2019) described such a solver guaranteeing 0.385-approximation for down-closed constraints, while Oveis Gharan and Vondr'ak (2011) showed that no solver can guarantee better than 0.478-approximation. In this paper, we present a solver guaranteeing 0.401-approximation, which significantly reduces the gap between the best known solver and the inapproximability result. The design and analysis of our solver are based on a novel bound that we prove for DR-submodular functions. This bound improves over a previous bound due to Feldman et al. (2011) that is used by essentially all state-of-the-art results for constrained maximization of general submodular/DR-submodular functions. Hence, we believe that our new bound is likely to find many additional applications in related problems, and to be a key component for further improvement.