Extension complexity of low-dimensional polytopes

DOI10.1090/TRAN/8614zbMATH Open1491.52012arXiv2006.08836OpenAlexW3034864005MaRDI QIDQ5082401FDOQ5082401

Authors: Matthew Kwan, Lisa Sauermann, Yufei Zhao 

Publication date: 16 June 2022

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

Abstract: Sometimes, it is possible to represent a complicated polytope as a projection of a much simpler polytope. To quantify this phenomenon, the extension complexity of a polytope $P$ is defined to be the minimum number of facets of a (possibly higher-dimensional) polytope from which $P$ can be obtained as a (linear) projection. This notion is motivated by its relevance to combinatorial optimisation, and has been studied intensively for various specific polytopes associated with important optimisation problems. In this paper we study extension complexity as a parameter of general polytopes, more specifically considering various families of low-dimensional polytopes. First, we prove that for a fixed dimension $d$, the extension complexity of a random $d$-dimensional polytope (obtained as the convex hull of random points in a ball or on a sphere) is typically on the order of the square root of its number of vertices. Second, we prove that any cyclic $n$-vertex polygon (whose vertices lie on a circle) has extension complexity at most $24sqrtn$. This bound is tight up to the constant factor $24$. Finally, we show that there exists an $n^{o(1)}$-dimensional polytope with at most $n$ vertices and extension complexity $n^{1-o(1)}$. Our theorems are proved with a range of different techniques, which we hope will be of further interest.

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

Recommendations

• Small extended formulations for cyclic polytopes
• Extension complexity of polytopes with few vertices or facets
• Extended formulations for polygons

zbMATH Keywords

combinatorial optimisationextension complexitylow-dimensional polytopes

Mathematics Subject Classification ID

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

Cites Work

• On the complexity of nonnegative matrix factorization
• Real rank versus nonnegative rank
• Intersection theorems with geometric consequences
• Expressing combinatorial optimization problems by linear programs
• Concentration inequalities using the entropy method
• An upper bound for nonnegative rank
• Constructing extended formulations from reflection relations
• On Polyhedral Approximations of the Second-Order Cone
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• Extended formulations for polygons
• Random polytopes, convex bodies, and approximation
• Combinatorial bounds on nonnegative rank and extended formulations
• Polygons as sections of higher-dimensional polytopes
• A short proof that the extension complexity of the correlation polytope grows exponentially
• Computing a nonnegative matrix factorization -- provably
• Heuristics for exact nonnegative matrix factorization
• Perturbation of matrices and nonnegative rank with a view toward statistical models
• On the nonnegative rank of distance matrices
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Extended formulations in combinatorial optimization
• The combinatorial structure of random polytopes
• Reformulation and decomposition of integer programs
• Title not available (Why is that?)
• Random polytopes
• Title not available (Why is that?)
• �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten
• Exponential lower bounds for polytopes in combinatorial optimization
• Combinatorics and probability. Abstracts from the workshop held April 14--20, 2013.
• Random points and lattice points in convex bodies
• Sur L'enveloppe convexe des nuages de points aleatoires dans Rⁿ. I
• Sharp concentration of random polytopes
• On the nonnegative rank of Euclidean distance matrices
• Which nonnegative matrices are slack matrices?
• Title not available (Why is that?)
• Stochastical approximation of convex bodies
• On the determinant of a sparse 0-1 matrix
• Extension complexity of polytopes with few vertices or facets
• An almost optimal algorithm for computing nonnegative rank
• Bounds on pairs of families with restricted intersections
• Few points to generate a random polytope
• Symmetry Matters for Sizes of Extended Formulations
• Recent results on random polytopes
• Euclidean distance matrices and separations in communication complexity theory
• Tropical lower bound for extended formulations. II: Deficiency graphs of matrices

Cited In (11)

• A geometric lower bound on the extension complexity of polytopes based on the \(f\)-vector
• Extended formulations for polygons
• Maximum semidefinite and linear extension complexity of families of polytopes
• Some problems related to extensions of polytopes
• Hidden vertices in extensions of polytopes
• On polyhedral extension of some LP theorems
• Complex psd-minimal polytopes in dimensions two and three
• Orthonormal representations, vector chromatic number, and extension complexity
• On the extension complexity of polytopes separating subsets of the Boolean cube
• Extension complexity of polytopes with few vertices or facets
• A separation between tropical matrix ranks

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

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