Concave Roofs and Downward Recovery for DR-Submodular Polynomial Maximization

Donglei Du

We give approximation algorithms for $\max\{F(x):x\in\K\}$, where $\K$ is a nonempty compact down-closed convex subset of the unit cube and $F$ is a nonnegative diminishing-returns…