# An improved approximation algorithm for maximizing a DR-submodular function over a convex set

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Mar 2022.

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

- [Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets](https://mlsanity.com/paper/2210.05965/) (2022)
- [A Unified Approach for Maximizing Continuous DR-submodular Functions](https://mlsanity.com/paper/2305.16671/) (2023)
- [Lyapunov function approach for approximation algorithm design and analysis: with applications in submodular maximization](https://mlsanity.com/paper/2205.12442/) (2022)
- [Boosting Gradient Ascent for Continuous DR-submodular Maximization](https://mlsanity.com/paper/2401.08330/) (2024)
- [Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization](https://mlsanity.com/paper/2403.10063/) (2024)
- [Bridging the Gap Between General and Down-Closed Convex Sets in Submodular Maximization](https://mlsanity.com/paper/2401.09251/) (2024)

## Abstract (arXiv)

Maximizing a DR-submodular function subject to a general convex set is an NP-hard problem arising from many applications in combinatorial optimization and machine learning. While it is highly desirable to design efficient approximation algorithms under this general setting where neither the objective function is monotonic nor the feasible set is down-closed, our main contribution is to present a 0.25-approximation Frank-Wolfe type of algorithm with a sub-exponential time-complexity under the value oracle model.