Combinatorial bounds on nonnegative rank and extended formulations
From MaRDI portal
Publication:1759811
DOI10.1016/j.disc.2012.09.015zbMath1259.90111arXiv1111.0444OpenAlexW1965650902MaRDI QIDQ1759811
Dirk Oliver Theis, Kanstantsin Pashkovich, Volker Kaibel, Samuel Fiorini
Publication date: 22 November 2012
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1111.0444
Boolean rankextended formulationsnonnegative rankbiclique covering in bipartite graphsprojections of polytopes
Related Items
The rectangle covering number of random Boolean matrices, Heuristics for exact nonnegative matrix factorization, Lifting for Simplicity: Concise Descriptions of Convex Sets, Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank, Extended formulations for independence polytopes of regular matroids, Common information and unique disjointness, Sparse sums of squares on finite abelian groups and improved semidefinite lifts, The (minimum) rank of typical fooling-set matrices, Extension complexity of low-dimensional polytopes, Polytopes of minimum positive semidefinite rank, Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes, On the combinatorial lower bound for the extension complexity of the spanning tree polytope, Lifts for Voronoi cells of lattices, The Nonnegative Rank of a Matrix: Hard Problems, Easy Solutions, Simple extensions of polytopes, Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes, On the extension complexity of polytopes separating subsets of the Boolean cube, On the complexity of Boolean matrix ranks, Fooling sets and the spanning tree polytope, The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract), Nondeterministic Communication Complexity of Random Boolean Functions (Extended Abstract), Nonnegative rank depends on the field, A geometric lower bound on the extension complexity of polytopes based on the \(f\)-vector, Extension complexity and realization spaces of hypersimplices, On the linear extension complexity of regular \(n\)-gons, Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization, Extended formulations for polygons, Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Factoring a band matrix over a semiring, Smallest compact formulation for the permutahedron, Lower bounds on nonnegative rank via nonnegative nuclear norms, Extended formulations, nonnegative factorizations, and randomized communication protocols, Uncapacitated flow-based extended formulations, Positive semidefinite rank, Worst-case results for positive semidefinite rank, On the Complexity of Robust PCA and ℓ1-Norm Low-Rank Matrix Approximation, On the linear extension complexity of stable set polytopes for perfect graphs, Extension Complexity of Polytopes with Few Vertices or Facets, Lower bounds on matrix factorization ranks via noncommutative polynomial optimization, Extended formulations of lower-truncated transversal polymatroids, Tropical lower bound for extended formulations. II. Deficiency graphs of matrices, Fooling-sets and rank, Small extended formulations for cyclic polytopes
