# Stronger Approximation Guarantees for Non-Monotone γ-Weakly DR-Submodular Maximization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 19 references that are in the map.
- First posted on arXiv 2 Jan 2026.

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

- [Continuous DR-submodular Maximization: Structure and Algorithms](https://mlsanity.com/paper/1711.02515/) (2017)
- [Constrained Submodular Maximization via New Bounds for DR-Submodular Functions](https://mlsanity.com/paper/2311.01129/) (2023)
- [A Unified Approach for Maximizing Continuous DR-submodular Functions](https://mlsanity.com/paper/2305.16671/) (2023)
- [Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization](https://mlsanity.com/paper/2403.10063/) (2024)

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

- [Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets](https://mlsanity.com/paper/2602.20578/) (2026)

## Abstract (arXiv)

Maximizing submodular objectives under constraints is a fundamental problem in machine learning and optimization. We study the maximization of a nonnegative, non-monotone γ-weakly DR-submodular function over a down-closed convex body. Our main result is an approximation algorithm whose guarantee depends smoothly on γ; in particular, when γ=1 (the DR-submodular case) our bound recovers the 0.401 approximation factor, while for γ<1 the guarantee degrades gracefully and, it improves upon previously reported bounds for γ-weakly DR-submodular maximization under the same constraints. Our approach combines a Frank-Wolfe-guided continuous-greedy framework with a γ-aware double-greedy step, yielding a simple yet effective procedure for handling non-monotonicity. This results in state-of-the-art guarantees for non-monotone γ-weakly DR-submodular maximization over down-closed convex bodies.