Bridging the Gap Between General and Down-Closed Convex Sets in
  Submodular Maximization
Loay Mualem Murad Tukan Moran Fledman
Optimization of DR-submodular functions has experienced a notable surge in
significance in recent times, marking a pivotal development within the domain
of non-convex optimization. Motivated by real-world scenarios, some recent
works have delved into the maximization of non-monotone DR-submodular functions
over general (not necessarily down-closed) convex set constraints. Up to this
point, these works have all used the minimum $\ell_\infty$ norm of any feasible
solution as a parameter. Unfortunately, a recent hardness result due to Mualem
\& Feldman~\cite{mualem2023resolving} shows that this approach cannot yield a
smooth interpolation between down-closed and non-down-closed constraints. In
this work, we suggest novel offline and online algorithms that provably provide
such an interpolation based on a natural decomposition of the convex body
constraint into two distinct convex bodies: a down-closed convex body and a
general convex body. We also empirically demonstrate the superiority of our
proposed algorithms across three offline and two online applications.