Smallest Compact Formulation for the Permutahedron
In this note, we consider the permutahedron, the convex hull of all permutations of {1,2…,n} . We show how to obtain an extended formulation for this polytope from any sorting network. By using the optimal Ajtai–Komlós–Szemerédi sorting network, this extended formulation has Θ(nlogn) variables and i...
| Hlavní autor: | |
|---|---|
| Další autoři: | |
| Médium: | Článek |
| Jazyk: | en_US |
| Vydáno: |
Springer-Verlag
2014
|
| On-line přístup: | http://hdl.handle.net/1721.1/87079 https://orcid.org/0000-0002-0520-1165 |