Back to Search
Start Over
A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs
- Publication Year :
- 2022
-
Abstract
- We consider the multilinear polytope defined as the convex hull of the set of binary points satisfying a collection of multilinear equations. The complexity of the facial structure of the multilinear polytope is closely related to the acyclicity degree of the underlying hypergraph. We obtain a polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs, hence characterizing the acyclic hypergraphs for which such a formulation can be constructed.
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2212.11239
- Document Type :
- Working Paper