论文标题
β-酰基超图的多连线多型的多项式大小的扩展配方
A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs
论文作者
论文摘要
我们认为定义为满足多线性方程组合的二进制点的凸壳的多线性多层。多线性多面体的面部结构的复杂性与基础超图的无环度密切相关。我们获得了β-酰基超图的多线性多型的多项式大小的扩展配方，因此表征了可以构建这种公式的无环性超图。
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.
