Symmetry in Extended Formulations of the Permutahedron

Details Symmetry in Extended Formulations of the Permutahedron Symmetry in Extended Formulations of the Permutahedron

2009-12-17

arxiv.org/abs/0912.3446v2

Mathematics

Combinatorics

corrected an error in the linear description of the permutahedron in introduction

Scientific paper

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 described a non-symmetric extended formulation of Pi_n 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 Pi_n.

Affiliated with

Also associated with

No associations

Rating

Symmetry in Extended Formulations of the Permutahedron does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Symmetry in Extended Formulations of the Permutahedron, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Symmetry in Extended Formulations of the Permutahedron will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-685994