Tropical lower bounds for extended formulations

DOI10.1007/s10107-014-0833-6zbMath1331.15021OpenAlexW2073007675MaRDI QIDQ745680

Yaroslav N. Shitov

Publication date: 14 October 2015

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-014-0833-6

zbMATH Keywords

convex polytopenonnegative matricesPuiseux seriesextension complexitytropical factorizationtropical operation

Mathematics Subject Classification ID

Factorization of matrices (15A23) Computational aspects related to convexity (52B55) Positive matrices and their generalizations; cones of matrices (15B48) Max-plus and related algebras (15A80)

Related Items (2)

Rank functions of tropical matrices ⋮ Tropical lower bound for extended formulations. II. Deficiency graphs of matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Polytopes of minimum positive semidefinite rank
• Tropical patterns of matrices and the Gondran-Minoux rank function
• Three notions of tropical rank for symmetric matrices
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• Extended formulations for polygons
• Tropical secant varieties of linear spaces
• Expressing combinatorial optimization problems by linear programs
• On the geometric interpretation of the nonnegative rank
• An upper bound for nonnegative rank
• The complexity of tropical matrix factorization
• Studying Non-negative Factorizations with Tools from Linear Algebra over a Semiring
• Algebraically Closed Fields Analogous to Fields of Puiseux Series
• Two Algorithmic Results for the Traveling Salesman Problem
• Lifts of Convex Sets and Cone Factorizations
• Computing a nonnegative matrix factorization -- provably
• Extended formulations in combinatorial optimization

This page was built for publication: Tropical lower bounds for extended formulations