Extended formulations for polygons

DOI10.1007/S00454-012-9421-9zbMATH Open1290.68122arXiv1107.0371OpenAlexW2095405086MaRDI QIDQ714985FDOQ714985

Authors: Samuel Fiorini, Thomas Rothvoß, Hans Raj Tiwary 

Publication date: 15 October 2012

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

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)$.

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

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

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)

Cites Work

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

Cited In (33)

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

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)