Abstract
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.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.