A geometric lower bound on the extension complexity of polytopes based on the \(f\)-vector
type: Item
instance of: scholarly article
title: A geometric lower bound on the extension complexity of polytopes based on the \(f\)-vector
zbMATH Open document ID: 1477.52016
author: Julien Dewez
author: Nicolas Gillis
author: François Glineur
published in: Discrete Applied Mathematics
publication date: 2021-09-15T00:00:00Z
Mathematics Subject Classification ID: 52B05
Mathematics Subject Classification ID: 52B55
zbMATH DE Number: 7395725
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: convex polytopes
zbMATH Keywords: linear extension
zbMATH Keywords: extended formulation
zbMATH Keywords: extension complexity
zbMATH Keywords: lower bound
zbMATH Keywords: \(f\)-vector
zbMATH Keywords: slack matrices
zbMATH Keywords: nonnegative matrix factorization
zbMATH Keywords: nonnegative rank
zbMATH Keywords: restricted nonnegative rank
MaRDI profile type: Publication
full work available at URL: j.dam.2020.09.028
OpenAlex ID: W3104490375
cites work: Computing a nonnegative matrix factorization -- provably
cites work: Generalized Dehn-Sommerville relations for polytopes, spheres and Eulerian partially ordered sets
cites work: Q4274011
cites work: A dual proof of the upper bound conjecture for convex polytopes.
cites work: On Restricted Nonnegative Matrix Factorization
cites work: Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
cites work: On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees
cites work: Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
cites work: Combinatorial bounds on nonnegative rank and extended formulations
cites work: On the geometric interpretation of the nonnegative rank
cites work: Smallest compact formulation for the permutahedron
cites work: Which nonnegative matrices are slack matrices?
cites work: Convex Polytopes
cites work: On low-dimensional faces that high-dimensional polytopes must have
cites work: The maximum numbers of faces of a convex polytope
cites work: The Matching Polytope has Exponential Extension Complexity
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: The upper bound theorem for polytopes: An easy proof of its asymptotic version
cites work: On the Complexity of Nonnegative Matrix Factorization
cites work: Expressing combinatorial optimization problems by linear programs
cites work: Lectures on Polytopes
DOI: 10.1016/J.DAM.2020.09.028
description: scientific article; zbMATH DE number 7395725