Extended Formulations for Polygons |
| |
Authors: | Samuel Fiorini Thomas Rothvo? Hans Raj Tiwary |
| |
Institution: | 1. Department of Mathematics, Universit?? Libre de Bruxelles, Brussels, Belgium 2. Department of Mathematics, MIT, Cambridge, USA
|
| |
Abstract: | 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(logn), a result originating from work by Ben-Tal and Nemirovski (Math. Oper. Res. 26(2), 193?C205, 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 an O(n)×O(n 2) integer grid with extension complexity $\varOmega (\sqrt{n}/\sqrt{\log n})$ . |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|