Extended formulations for polygons

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(\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})$.

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

References in corpus (1)

• Some 0/1 polytopes need exponential size extended formulations

Cited by in corpus (17)

• Heuristics for Exact Nonnegative Matrix Factorization
• Introduction to Nonnegative Matrix Factorization
• On the existence of 0/1 polytopes with high semidefinite extension complexity
• The matching polytope does not admit fully-polynomial size relaxation schemes
• Algorithms for Positive Semidefinite Factorization
• The matching polytope has exponential extension complexity
• Combinatorial Bounds on Nonnegative Rank and Extended Formulations
• Polytopes of Minimum Positive Semidefinite Rank
• Worst-Case Results For Positive Semidefinite Rank
• On the Linear Extension Complexity of Regular n-gons
• Small Extended Formulations for Cyclic Polytopes
• Realizability of Polytopes as a Low Rank Matrix Completion Problem
• Equivariant semidefinite lifts of regular polygons
• A Singly-Exponential Time Algorithm for Computing Nonnegative Rank
• Embedding Formulations and Complexity for Unions of Polyhedra
• An upper bound for nonnegative rank
• Complexity of LP in Terms of the Face Lattice