Tropical lower bounds for extended formulations

DOI10.1007/S10107-014-0833-6zbMATH Open1331.15021OpenAlexW2073007675MaRDI QIDQ745680FDOQ745680

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

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

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)

Cites Work

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

Cited In (3)

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

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)