Concave Roofs and Downward Recovery for DR-Submodular Polynomial Maximization

Abstract

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 (DR) submodular polynomial: every entry of its Hessian is nonpositive on the cube. Starting from quadratic or cubic coefficients, we decompose the objective exactly into nonnegative rooted atoms and affine terms. Concave upper bounds for these components give a tractable roof. We then decrease the coordinates of a roof optimizer using maps that work for all components at once, recovering a fraction of the roof value while preserving feasibility. For quadratics, we also retain the concave diagonal residual exactly. Under the stated assumptions on optimization access, these constructions give deterministic polynomial-time factors of $1/2$ for quadratics and $8/17$ for cubics, up to any prescribed additive error. The cubic result includes positive cubic coefficients and repeated variables. The factor $8/17$ also holds for two larger classes: supplied compatible rooted certificates of literal degree at most twelve, and sums of nonnegative submodular local functions of arity at most four. At arbitrary finite literal degree, a common scalar map attains the optimal single-map factor $2\sqrt3-3$. Global monotonicity and concave-cardinality structure give stronger guarantees for multilinear local-function sums, with no recovery beyond the identity map. Standard matroid rounding transfers the multilinear guarantees without loss. We also prove online preservation for directed-hypergraph cuts and, separately, a Unique-Games inapproximability bound of approximately $0.82843$ for explicit quadratic input under a cardinality upper bound.