A geometric lower bound on the extension complexity of polytopes based on the \(f\)-vector
DOI10.1016/j.dam.2020.09.028zbMath1477.52016OpenAlexW3104490375MaRDI QIDQ1983109
Julien Dewez, François Glineur, Nicolas Gillis
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
combinatorial optimization\(f\)-vectorlower boundconvex polytopesnonnegative matrix factorizationextension complexitynonnegative rankslack matriceslinear extensionextended formulationrestricted nonnegative rank
Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Computational aspects related to convexity (52B55)
Related Items (1)
Cites Work
- Unnamed Item
- Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
- Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
- Smallest compact formulation for the permutahedron
- Generalized Dehn-Sommerville relations for polytopes, spheres and Eulerian partially ordered sets
- Expressing combinatorial optimization problems by linear programs
- On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees
- On the geometric interpretation of the nonnegative rank
- Combinatorial bounds on nonnegative rank and extended formulations
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- The upper bound theorem for polytopes: An easy proof of its asymptotic version
- Which nonnegative matrices are slack matrices?
- On low-dimensional faces that high-dimensional polytopes must have
- On the Complexity of Nonnegative Matrix Factorization
- A dual proof of the upper bound conjecture for convex polytopes.
- Lectures on Polytopes
- Convex Polytopes
- On Restricted Nonnegative Matrix Factorization
- The Matching Polytope has Exponential Extension Complexity
- Computing a nonnegative matrix factorization -- provably
- The maximum numbers of faces of a convex polytope
This page was built for publication: A geometric lower bound on the extension complexity of polytopes based on the \(f\)-vector
