A geometric lower bound on the extension complexity of polytopes based on the f-vector

DOI10.1016/J.DAM.2020.09.028zbMATH Open1477.52016OpenAlexW3104490375MaRDI QIDQ1983109FDOQ1983109

Authors: Julien Dewez, Nicolas Gillis, François Glineur 

Publication date: 15 September 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2020.09.028

Recommendations

• On ranks of regular polygons
• On the linear extension complexity of regular \(n\)-gons
• Combinatorial bounds on nonnegative rank and extended formulations
• Maximum semidefinite and linear extension complexity of families of polytopes
• Extension complexity of low-dimensional polytopes

zbMATH Keywords

combinatorial optimizationnonnegative matrix factorizationlower boundconvex polytopes\(f\)-vectorextension complexitynonnegative rankslack matriceslinear extensionextended formulationrestricted nonnegative rank

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Computational aspects related to convexity (52B55)

Cites Work

• On the complexity of nonnegative matrix factorization
• Computing a nonnegative matrix factorization -- provably
• Lectures on Polytopes
• Expressing combinatorial optimization problems by linear programs
• On the geometric interpretation of the nonnegative rank
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• Convex Polytopes
• The maximum numbers of faces of a convex polytope
• Combinatorial bounds on nonnegative rank and extended formulations
• Smallest compact formulation for the permutahedron
• Generalized Dehn-Sommerville relations for polytopes, spheres and Eulerian partially ordered sets
• Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
• The upper bound theorem for polytopes: An easy proof of its asymptotic version
• Title not available (Why is that?)
• On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees
• Which nonnegative matrices are slack matrices?
• On restricted nonnegative matrix factorization
• On low-dimensional faces that high-dimensional polytopes must have
• A dual proof of the upper bound conjecture for convex polytopes.

Cited In (5)

• Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes
• Complexity yardsticks for \(f\)-vectors of polytopes and spheres
• Conic optimization-based algorithms for nonnegative matrix factorization
• On the linear extension complexity of regular \(n\)-gons
• On ranks of regular polygons

This page was built for publication: A geometric lower bound on the extension complexity of polytopes based on the \(f\)-vector

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