Concave Roofs and Downward Recovery for DR-Submodular Polynomial Maximization
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.04027
curl -X POST /api/v1/records/arxiv/2610.04027/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.04027/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'