Extended formulations for polygons

Details Extended formulations for polygons Extended formulations for polygons

2011-07-02

arxiv.org/abs/1107.0371v2

Computer Science

Discrete Mathematics

10 pages, 2 figures; Revised version accepted for publication in Discrete & Computational Geometry

Scientific paper

The extension complexity of a polytope $P$ is the smallest integer $k$ such that $P$ is the projection of a polytope $Q$ with $k$ facets. We study the extension complexity of $n$-gons in the plane. First, we give a new proof that the extension complexity of regular $n$-gons is $O(\log n)$, a result originating from work by Ben-Tal and Nemirovski (2001). Our proof easily generalizes to other permutahedra and simplifies proofs of recent results by Goemans (2009), and Kaibel and Pashkovich (2011). Second, we prove a lower bound of $\sqrt{2n}$ on the extension complexity of generic $n$-gons. Finally, we prove that there exist $n$-gons whose vertices lie on a $O(n) \times O(n^2)$ integer grid with extension complexity $\Omega(\sqrt{n}/\sqrt{\log n})$.

Affiliated with

Also associated with

No associations

Rating

Extended formulations for polygons 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 Extended formulations for polygons, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extended formulations for polygons will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-175197