Delphi.science

The One-Skeleton of Multilinear Polytopes and Their Standard Relaxations

Source: arxiv.org/abs/2611.15785

Alberto Del Pia, Zihong Xu

arXivarxiv/2611.15785Nov 11, 2026math.OCscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

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}'