Tight Lower Bounds on the Sizes of Symmetric Extensions of Permutahedra and Similar Results
成果类型：
Article
署名作者：
Pashkovich, Kanstantsin
署名单位：
Universite Libre de Bruxelles
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.2014.0659
发表日期：
2014
页码：
1330-1339
关键词：
摘要：
It is well known that the permutahedron IIn has 2(n) - 2 facets. The Birkhoff polytope provides a symmetric extended formulation of IIn of size Theta(n(2)). Recently, Goemans described a non-symmetric extended formulation of IIn of size Theta(n log n). In this paper, we prove that Omega(n(2)) is a lower bound for the size of symmetric extended formulations of IIn. 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.
来源URL：