The One-Skeleton of Multilinear Polytopes and Their Standard Relaxations
Source: arxiv.org/abs/2611.15785
Edge-following methods, such as the simplex method, move along edges of a polytope. Their behavior depends on which vertices are adjacent and on the diameter. We study both for the two polytopes of binary polynomial optimization: the multilinear polytope and its standard linear relaxation. For quadratic polynomials, Padberg showed that two integral vertices are adjacent in both polytopes if and only if the variables where they differ induce a connected subgraph. For higher degree, we replace this subgraph by a contracted hypergraph on the same variables, built from the monomials whose…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.15785
curl -X POST /api/v1/records/arxiv/2611.15785/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.15785/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'