A 0.4584-approximation for DR-submodular maximization over down-closed convex sets

Abstract

We obtain a $0.4584$-approximation for nonnegative, non-monotone, $L$-smooth DR-submodular maximization over compact convex down-closed subsets of the unit cube, improving the $4/9\approx 0.4444$ ratio of Aggarwal's projection-based algorithm~\cite{aggarwal2026geometry}. A recovery map combining exponential and linear-fractional branches admits a cube-wide affine upper bound. The resulting continuous-time Frank--Wolfe-type algorithm with randomized output and its randomized discrete-time implementation both satisfy $\E F(\widehat x)\ge(0.4584-\varepsilon)\OPT-δLD^2$; the implementation uses polynomially many cube-wide value/full-gradient queries and ordinary linear maximization calls, where $D$ is the feasible diameter and $\epsilon ,\delta >0$ are accuracy parameters. Our guarantee and Aggarwal's hardness bound~\cite{aggarwal2026geometry} place the optimal approximation ratio for cube-wide value/full-gradient queries and linear maximization, with additive error $\delta L{D}^2$, in $[0.4584,0.4705)$. Standard multilinear sampling and pipage rounding imply an expected $(0.4584-\epsilon )$-approximation for nonnegative submodular set-function maximization under a matroid constraint \cite[Lemma B.3]{vondrak2013symmetry}.