Extension complexity of low-dimensional polytopes

DOI10.1090/TRAN/8614MaRDI QIDQ5082401zbMATH OpenOpenAlexFDO

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)

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

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)

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.

Recommendations

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

Cites work

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

Cited in

(11)

• A separation between tropical matrix ranks
• 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

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)