Extension complexity of polytopes with few vertices or facets

DOI10.1137/16M1063721MaRDI QIDQ2835841zbMATH OpenFDO

Authors Arnau Padrol

Publication date 30 November 2016

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

extended formulationextension complexitygale transformpolytope with few verticesrealization space

Mathematics Subject Classification ID

(n)-dimensional polytopes (52B11) Gale and other diagrams (52B35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Abstract: We study the extension complexity of polytopes with few vertices or facets. On the one hand, we provide a complete classification of $d$-polytopes with at most $d+4$ vertices according to their extension complexity: Out of the super-exponentially many $d$-polytopes with $d+4$ vertices, all have extension complexity $d+4$ except for some families of size $heta(d^2)$. On the other hand, we show that generic realizations of simplicial/simple $d$-polytopes with $d+1+alpha$ vertices/facets have extension complexity at least $2sqrtd(d+alpha)-d+1$, which shows that for all $d>(fracalpha-12{)}^2$ there are $d$-polytopes with $d+1+alpha$ vertices or facets and extension complexity $d+1+alpha$.

Recommendations

• Extension complexity of low-dimensional polytopes
• Small extended formulations for cyclic polytopes
• Extended formulations for polygons

Cites work

• An upper bound for nonnegative rank
• Combinatorial bounds on nonnegative rank and extended formulations
• Construction and analysis of projected deformed products
• Convex Polytopes
• Counting d-polytopes with d+3 vertices
• Expressing combinatorial optimization problems by linear programs
• Extended formulations for polygons
• Extended formulations in combinatorial optimization
• Extension complexity and realization spaces of hypersimplices
• Heuristics for exact nonnegative matrix factorization
• scientific article; zbMATH DE number 4092241 (Why is no real title available?)
• scientific article; zbMATH DE number 3696001 (Why is no real title available?)
• scientific article; zbMATH DE number 1201576 (Why is no real title available?)
• scientific article; zbMATH DE number 2107521 (Why is no real title available?)
• Lectures on Polytopes
• Lifts of Convex Sets and Cone Factorizations
• Many neighborly polytopes and oriented matroids
• Nonnegative matrix factorization requires irrationality
• Nonnegative rank depends on the field
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• Polygons as sections of higher-dimensional polytopes
• Polytopes with few vertices and few facets
• Projected products of polygons
• Real rank versus nonnegative rank
• Realization spaces of polytopes
• Some Applications of Affine Gale Diagrams to Polytopes with Few Vertices
• Triangulations. Structures for algorithms and applications

Cited in

(14)

• Maximum semidefinite and linear extension complexity of families of polytopes
• Euclidean distance matrices and separations in communication complexity theory
• On Dantzig figures from graded lexicographic orders
• Extension complexity and realization spaces of hypersimplices
• Hidden vertices in extensions of polytopes
• Complexity yardsticks for \(f\)-vectors of polytopes and spheres
• Extension complexities of Cartesian products involving a pyramid
• Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
• Tropical lower bound for extended formulations. II: Deficiency graphs of matrices
• Extension complexity of low-dimensional polytopes
• Complex psd-minimal polytopes in dimensions two and three
• On the extension complexity of polytopes separating subsets of the Boolean cube
• Extended formulations for polygons
• Sublinear extensions of polygons

This page was built for publication: Extension complexity of polytopes with few vertices or facets

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