Concave Roofs and Downward Recovery for DR-Submodular Polynomial Maximization
Abstract
We give approximation algorithms for max{F(x):x∈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√3−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.
Related
- An Analytic 0.48-Approximation for Non-Monotone k-Submodular Maximization under a Matroid Constraint
- Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization
- On Exact Dual and Mixed-Integer Reformulations for Finite Horizon Markov Decision Processes with Submodular Revenue Maximization
- A Deterministic $0.401$-Approximation for Non-monotone Submodular Maximization under Matroid Constraints
- Online Submodular Welfare Maximization: Computation is not the Bottleneck
BibTeX
@misc{du2026concave,
title = {{Concave Roofs and Downward Recovery for DR-Submodular Polynomial Maximization}},
author = {Donglei Du},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04027},
eprint = {2610.04027},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04027},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Concave Roofs and Downward Recovery for DR-Submodular Polynomial Maximization
AU - Donglei Du
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.04027
UR - https://arxiv.org/abs/2610.04027
AB - We give approximation algorithms for max{F(x):x∈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√3−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.
ER -