Tight Lower Bounds on the Sizes of Symmetric Extensions of Permutahedra and Similar Results
Tight Lower Bounds on the Sizes of Symmetric Extensions of Permutahedra and Similar Results
复制标题
全面体对称扩展尺寸的严格下界及类似结果
DOI：
--
复制
发表时间：
2009
影响因子：
1.7
通讯作者：
Kanstantsin Pashkovich
中科院分区：
文献类型：
--
作者：
Kanstantsin Pashkovich
众所周知，置换面体n有2n − 2个面。Birkhoff多面体提供大小为θ（n2）的对称扩展公式。最近，Goemans描述了大小为Θ（n log n）的非对称扩展公式。本文证明了Ω（n2）是n的对称扩展公式的大小的下界。此外，我们证明了基数指示多面体具有相同的紧下界的对称和非对称的扩展公式的大小为置换面体。
It is well known that the permutahedron Πn has 2n − 2 facets. The Birkhoff polytope provides a symmetric extended formulation of Πn of size Θ(n2). Recently, Goemans described a non-symmetric extended formulation of Πn of size Θ(n log n). In this paper, we prove that Ω(n2) is a lower bound for the size of symmetric extended formulations of Πn. Moreover, we prove that the cardinality indicating polytope has the same tight lower bounds for the sizes of symmetric and nonsymmetric extended formulations as the permutahedron.