Smallest compact formulation for the permutahedron
成果类型：
Article
署名作者：
Goemans, Michel X.
署名单位：
Massachusetts Institute of Technology (MIT)
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-014-0757-1
发表日期：
2015
页码：
5-11
关键词：
摘要：
In this note, we consider the permutahedron, the convex hull of all permutations of . We show how to obtain an extended formulation for this polytope from any sorting network. By using the optimal Ajtai-Komls-Szemer,di sorting network, this extended formulation has variables and inequalities. Furthermore, from basic polyhedral arguments, we show that this is best possible (up to a multiplicative constant) since any extended formulation has at least inequalities. The results easily extend to the generalized permutahedron.