Tropical lower bounds for extended formulations

DOI10.1007/S10107-014-0833-6MaRDI QIDQ745680zbMATHOpenAlexFDO

Authors Ya. 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

nonnegative matricesconvex polytopeextension complexityPuiseux seriestropical factorizationtropical operation

Mathematics Subject Classification ID

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

Recommendations

• Tropical lower bound for extended formulations. II: Deficiency graphs of matrices
• What Tropical Geometry Tells Us about the Complexity of Linear Programming
• Combinatorial bounds on nonnegative rank and extended formulations
• Tropical convexity
• The tropical double description method

Cites work

• scientific article; zbMATH DE number 3813580 (Why is no real title available?)
• scientific article; zbMATH DE number 5019906 (Why is no real title available?)
• Algebraically Closed Fields Analogous to Fields of Puiseux Series
• An upper bound for nonnegative rank
• Computing a nonnegative matrix factorization -- provably
• Expressing combinatorial optimization problems by linear programs
• Extended formulations for polygons
• Extended formulations in combinatorial optimization
• Lifts of Convex Sets and Cone Factorizations
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• On the geometric interpretation of the nonnegative rank
• Polytopes of minimum positive semidefinite rank
• Studying non-negative factorizations with tools from linear algebra over a semiring
• The complexity of tropical matrix factorization
• Three notions of tropical rank for symmetric matrices
• Tropical patterns of matrices and the Gondran-Minoux rank function
• Tropical secant varieties of linear spaces
• Two Algorithmic Results for the Traveling Salesman Problem

Cited in

(4)

• Rank functions of tropical matrices
• Upper and lower bounds for Grigoriev's algorithm for solving integral tropical linear systems
• Tropical lower bound for extended formulations. II: Deficiency graphs of matrices
• Lower bounds for tropical circuits and dynamic programs

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

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