Complexity of solving tropical linear systems

DOI10.1007/s00037-012-0053-5zbMath1282.68137MaRDI QIDQ1947044

Dima Yu. Grigoriev

Publication date: 11 April 2013

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-012-0053-5

zbMATH Keywords

Kapranov rank; tropical rank; complexity of solving; tropical linear systems

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

15A80: Max-plus and related algebras

Related Items

New algorithms for solving tropical linear systems, Towards an operad-based cryptography: applications of commutative operads, Tropical differential equations, Upper and lower bounds for Grigoriev's algorithm for solving integral tropical linear systems, Bounds on the number of connected components for tropical prevarieties, An algorithm for solving an overdetermined tropical linear system using the analysis of stable solutions of subsystems, Tropical effective primary and dual Nullstellensätze, Complexity of deciding whether a tropical linear prevariety is a tropical variety, A characterization of bases of tropical kernels in terms of Cramer's rule, Abstract tropical linear programming, Tropical combinatorial Nullstellensatz and sparse polynomials, Complexity of tropical and MIN-plus linear prevarieties

Cites Work

• Unnamed Item
• Unnamed Item
• Exponential behaviour of the Butkovič-Zimmermann algorithm for solving two-sided linear systems in max-algebra
• A condition for the strong regularity of matrices in the minimax algebra
• Complexity of tropical and MIN-plus linear prevarieties
• On the frontiers of polynomial computations in tropical geometry
• Computing tropical varieties
• A strongly polynomial algorithm for solving two-sided linear systems in max-algebra
• TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES
• Max-linear Systems: Theory and Algorithms
• The Tropical Rank of a Tropical Matrix
• Kapranov rank vs. tropical rank