Improved approximation algorithm advances submodular optimization accuracy
A 0.4584-approximation for DR-submodular maximization over down-closed convex sets
Data Structures and Algorithms
Summary
Maximizing certain complex functions that model real-world problems can be hard, and finding good approximate solutions is important. This paper improves the best known method for maximizing these functions under specific constraints, getting closer to the optimal answer. The authors describe a new algorithm that achieves a better approximation ratio than previous approaches and show it can be implemented efficiently with a controlled error. This advancement narrows the gap between what is achievable and what is theoretically impossible for these optimization problems.
What this means in practice
- •For machine learning engineers: Optimize complex, constrained set functions more accurately for feature selection and resource allocation tasks.
- •For operations research teams: Improve solution quality in diverse combinatorial optimization problems under convex constraints using enhanced algorithms.
A theory result. No direct application yet.
Authors
Donglei Du
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\approx0.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 $\varepsilon,δ>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 $δLD^2$, in $[0.4584,0.4705)$. Standard multilinear sampling and pipage rounding imply an expected $(0.4584-\varepsilon)$-approximation for nonnegative submodular set-function maximization under a matroid constraint \cite[Lemma B.3]{vondrak2013symmetry}.