Extension Complexity of Polytopes with Few Vertices or Facets

DOI10.1137/16M1063721zbMath1354.52014arXiv1602.06894MaRDI QIDQ2835841

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

extension complexityextended formulationgale transformrealization spacepolytope with few vertices

Mathematics Subject Classification ID

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

Related Items (8)

Extension complexity of low-dimensional polytopes ⋮ Complex psd-minimal polytopes in dimensions two and three ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ 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 ⋮ Tropical lower bound for extended formulations. II. Deficiency graphs of matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polytopes with few vertices and few facets
• Heuristics for exact nonnegative matrix factorization
• Many neighborly polytopes and oriented matroids
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• Extended formulations for polygons
• Counting \(d\)-polytopes with \(d+3\) vertices
• Construction and analysis of projected deformed products
• Triangulations. Structures for algorithms and applications
• Real rank versus nonnegative rank
• Expressing combinatorial optimization problems by linear programs
• Extension complexity and realization spaces of hypersimplices
• Combinatorial bounds on nonnegative rank and extended formulations
• Nonnegative rank depends on the field
• Polygons as sections of higher-dimensional polytopes
• An upper bound for nonnegative rank
• Realization spaces of polytopes
• Some Applications of Affine Gale Diagrams to Polytopes with Few Vertices
• Lectures on Polytopes
• Convex Polytopes
• Projected products of polygons
• Lifts of Convex Sets and Cone Factorizations
• Nonnegative Matrix Factorization Requires Irrationality
• Extended formulations in combinatorial optimization

This page was built for publication: Extension Complexity of Polytopes with Few Vertices or Facets