44 citations · 80 across the 32 of their papers we have counts for
Showing 2009Show all
2 papers · 1 filter
math.CO2009★ 5 cited
Tight Lower Bounds on the Sizes of Symmetric Extensions of Permutahedra and Similar Results
Kanstantsin Pashkovich
It is well known that the permutahedron Pi_n has 2^n-2 facets. The Birkhoff polytope provides a symmetric extended formulation of Pi_n of size Theta(n^2). Recently, Goemans describ…
math.CO2009★ 44 cited
Symmetry Matters for Sizes of Extended Formulations
Volker Kaibel, Kanstantsin Pashkovich, Dirk Oliver Theis
In 1991, Yannakakis (J. Comput. System Sci., 1991) proved that no symmetric extended formulation for the matching polytope of the complete graph K_n with n nodes has a number of va…