Extension complexity of low-dimensional polytopes

DOI10.1090/tran/8614zbMath1491.52012arXiv2006.08836OpenAlexW3034864005MaRDI QIDQ5082401

Matthew Kwan, Lisa Sauermann, Yufei Zhao

Publication date: 16 June 2022

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial optimisationextension complexitylow-dimensional polytopes

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Combinatorial optimization (90C27)

Related Items (2)

A separation between tropical matrix ranks ⋮ On the extension complexity of polytopes separating subsets of the Boolean cube

Cites Work

• Heuristics for exact nonnegative matrix factorization
• Combinatorics and probability. Abstracts from the workshop held April 14--20, 2013.
• On the nonnegative rank of distance matrices
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• The combinatorial structure of random polytopes
• Extended formulations for polygons
• On the determinant of a sparse 0-1 matrix
• Stochastical approximation of convex bodies
• Sharp concentration of random polytopes
• On the nonnegative rank of Euclidean distance matrices
• Real rank versus nonnegative rank
• Intersection theorems with geometric consequences
• Expressing combinatorial optimization problems by linear programs
• Concentration inequalities using the entropy method
• Euclidean distance matrices and separations in communication complexity theory
• Combinatorial bounds on nonnegative rank and extended formulations
• Bounds on pairs of families with restricted intersections
• Polygons as sections of higher-dimensional polytopes
• A short proof that the extension complexity of the correlation polytope grows exponentially
• An upper bound for nonnegative rank
• Which nonnegative matrices are slack matrices?
• Exponential Lower Bounds for Polytopes in Combinatorial Optimization
• Computing a Nonnegative Matrix Factorization---Provably
• Extension Complexity of Polytopes with Few Vertices or Facets
• Constructing Extended Formulations from Reflection Relations
• Tropical lower bound for extended formulations. II. Deficiency graphs of matrices
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Perturbation of Matrices and Nonnegative Rank with a View toward Statistical Models
• Random points and lattice points in convex bodies
• Reformulation and Decomposition of Integer Programs
• On the Complexity of Nonnegative Matrix Factorization
• Few points to generate a random polytope
• The Matching Polytope has Exponential Extension Complexity
• Symmetry Matters for Sizes of Extended Formulations
• Random Polytopes
• Sur L'enveloppe convexe des nuages de points aleatoires dans Rⁿ. I
• On Polyhedral Approximations of the Second-Order Cone
• [https://portal.mardi4nfdi.de/wiki/Publication:5728818 �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten]
• An Almost Optimal Algorithm for Computing Nonnegative Rank
• Extended formulations in combinatorial optimization
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Extension complexity of low-dimensional polytopes