Upper and lower bounds for Grigoriev's algorithm for solving integral tropical linear systems

DOI10.1007/S10958-013-1395-5MaRDI QIDQ376127zbMATH OpenOpenAlexFDO

Authors A. P. Davydow

Publication date 4 November 2013

Published in Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10958-013-1395-5

zbMATH Keywords

Grigoriev's algorithmintegral tropical linear systemslower boundstime complexityupper bounds

Mathematics Subject Classification ID

Max-plus and related algebras (15A80) Complexity and performance of numerical algorithms (65Y20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Symbolic computation and algebraic computation (68W30) Analysis of algorithms (68W40)

Recommendations

• New algorithms for solving tropical linear systems
• Complexity of solving tropical linear systems
• Upper bounds on the complexity of solving systems of linear equations
• A note on tropical linear and integer programs
• Tropical lower bounds for extended formulations
• An algorithm for solving an overdetermined tropical linear system using the analysis of stable solutions of subsystems
• Solving linear systems over tropical semirings through normalization method and its applications
• On the maximal solution of a linear system over tropical semirings
• Abstract tropical linear programming
• Upper bounds on the magnitude of solutions of certain linear systems with integer coefficients

Cites work

• A condition for the strong regularity of matrices in the minimax algebra
• A Polyhedral Method for Solving Sparse Polynomial Systems
• Complexity of solving tropical linear systems
• Tropical Cryptography

Cited in

(5)

• An algorithm for solving an overdetermined tropical linear system using the analysis of stable solutions of subsystems
• Towards an operad-based cryptography: applications of commutative operads
• New algorithms for solving tropical linear systems
• An algorithm to describe the solution set of any tropical linear system A x = B x
• On max-plus two-sided linear systems whose solution sets are min-plus linear

This page was built for publication: Upper and lower bounds for Grigoriev's algorithm for solving integral tropical linear systems

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