Extended formulations for polygons

DOI10.1007/S00454-012-9421-9MaRDI QIDQ714985zbMATH OpenOpenAlexFDO

Authors Samuel Fiorini, Thomas Rothvoß, Hans Raj Tiwary

Publication date 15 October 2012

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.0371

zbMATH Keywords

lower boundpolytopeextended formulationspolygon

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05)

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 (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 $sqrt2n$ on the extension complexity of generic $n$-gons. Finally, we prove that there exist $n$-gons whose vertices lie on a $O(n)imesO(n^2)$ integer grid with extension complexity $Omega(sqrtn/sqrtlogn)$.

Recommendations

• On the linear extension complexity of regular \(n\)-gons
• Small extended formulations for cyclic polytopes
• Extension complexity of low-dimensional polytopes
• On ranks of regular polygons
• Extension complexity of polytopes with few vertices or facets

Cites work

• scientific article; zbMATH DE number 1703931 (Why is no real title available?)
• scientific article; zbMATH DE number 1955467 (Why is no real title available?)
• scientific article; zbMATH DE number 1466163 (Why is no real title available?)
• Combinatorial bounds on nonnegative rank and extended formulations
• Constructing extended formulations from reflection relations
• Expressing combinatorial optimization problems by linear programs
• Extended formulations in combinatorial optimization
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• On Polyhedral Approximations of the Second-Order Cone
• Reformulation and decomposition of integer programs
• Smallest compact formulation for the permutahedron
• Some \(0/1\) polytopes need exponential size extended formulations
• Sorting in \(c \log n\) parallel steps
• Using separation algorithms to generate mixed integer model reformulations

Cited in

(39)

• Computing a nonnegative matrix factorization -- provably
• Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
• Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
• Extension complexity of low-dimensional polytopes
• Euclidean distance matrices and separations in communication complexity theory
• Regular matroids have polynomial extension complexity
• Extension complexity of polytopes with few vertices or facets
• Realizability of polytopes as a low rank matrix completion problem
• Extension complexity of formal languages
• Heuristics for exact nonnegative matrix factorization
• Small extended formulations for cyclic polytopes
• Extended formulations for Gomory corner polyhedra
• An upper bound for nonnegative rank
• On the existence of 0/1 polytopes with high semidefinite extension complexity
• Extension complexity and realization spaces of hypersimplices
• Smallest compact formulation for the permutahedron
• Maximum semidefinite and linear extension complexity of families of polytopes
• On ranks of regular polygons
• Tropical lower bound for extended formulations. II: Deficiency graphs of matrices
• Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes
• Tropical lower bounds for extended formulations
• Worst-case results for positive semidefinite rank
• An almost optimal algorithm for computing nonnegative rank
• Formulas for right-angled hyperbolic polygons
• Extension complexities of Cartesian products involving a pyramid
• Some \(0/1\) polytopes need exponential size extended formulations
• Polytopes of minimum positive semidefinite rank
• Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes
• Circuits in extended formulations
• Extended formulations in combinatorial optimization
• Polyhedral approximation of ellipsoidal uncertainty sets via extended formulations: a computational case study
• Algorithms for positive semidefinite factorization
• On the linear extension complexity of regular \(n\)-gons
• Extended formulations for convex heptagons
• Hidden vertices in extensions of polytopes
• On permuting some coordinates of polytopes
• Common information and unique disjointness
• On the extension complexity of polytopes separating subsets of the Boolean cube
• Polygons as sections of higher-dimensional polytopes

This page was built for publication: Extended formulations for polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714985)