A strongly polynomial algorithm for solving two-sided linear systems in max-algebra

DOI10.1016/j.dam.2005.09.008zbMath1090.68119OpenAlexW2157261308MaRDI QIDQ2489939

Karel Zimmermann, Peter Butkovic

Publication date: 28 April 2006

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2005.09.008

zbMATH Keywords

Max-algebraStrongly polynomial algorithmTwo-sided equation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Discrete event control/observation systems (93C65)

Related Items

TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES ⋮ A uniform synchronization problem over max-plus algebra ⋮ AE solutions to two-sided interval linear systems over max-plus algebra ⋮ A note on a paper by E. Khorram and A. Ghodousian ⋮ Idempotent and tropical mathematics; complexity of algorithms and interval analysis ⋮ Optimization problems under (max, min)-linear equations and/or inequality constraints ⋮ Log-Barrier Interior Point Methods Are Not Strongly Polynomial ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Abstract tropical linear programming ⋮ On the greatest solutions to weakly linear systems of fuzzy relation inequalities and equations ⋮ On the solution of a two-sided vector equation in tropical algebra ⋮ Complexity of solving tropical linear systems ⋮ Weak dual residuations applied to tropical linear equations ⋮ Complete solution of tropical vector inequalities using matrix sparsification. ⋮ What Tropical Geometry Tells Us about the Complexity of Linear Programming ⋮ An algorithm to describe the solution set of any tropical linear system \(A \odot x = B \odot x\) ⋮ On max-min linear inequalities and coalitional resource games with sharable resources ⋮ Hard problems in max-algebra, control theory, hypergraphs and other areas ⋮ Quantitative simulations by matrices ⋮ Exponential behaviour of the Butkovič-Zimmermann algorithm for solving two-sided linear systems in max-algebra ⋮ An algorithm for solving two-sided interval system of max-plus linear equations

Cites Work

• Linear and combinatorial optimization in ordered algebraic structures
• The equation \(A \otimes x = B \otimes y\) over \((\max,+)\)
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A strongly polynomial algorithm for solving two-sided linear systems in max-algebra