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

DOI10.1016/J.DAM.2005.09.008zbMATH Open1090.68119OpenAlexW2157261308MaRDI QIDQ2489939FDOQ2489939

Authors: Karel Zimmermann, Peter Butkovič 

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

Recommendations

• scientific article
• Solving systems of two-sided (max, min)-linear equations
• The equation \(A \otimes x = B \otimes y\) over \((\max,+)\)
• On two-sided max-linear equations
• Exponential behaviour of the Butkovič-Zimmermann algorithm for solving two-sided linear systems in max-algebra

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)

Cites Work

• Title not available (Why is that?)
• Linear and combinatorial optimization in ordered algebraic structures
• The equation \(A \otimes x = B \otimes y\) over \((\max,+)\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (29)

• A uniform synchronization problem over max-plus algebra
• AE solutions to two-sided interval linear systems over max-plus algebra
• Title not available (Why is that?)
• Title not available (Why is that?)
• An algorithm to describe the solution set of any tropical linear system \(A \odot x = B \odot x\)
• What Tropical Geometry Tells Us about the Complexity of Linear Programming
• Simulations and bisimulations for max-plus automata
• Solving systems of two-sided (max, min)-linear equations
• On the greatest solutions to weakly linear systems of fuzzy relation inequalities and equations
• Idempotent and tropical mathematics; complexity of algorithms and interval analysis
• Abstract tropical linear programming
• Complete solution of tropical vector inequalities using matrix sparsification.
• An algorithm for solving two-sided interval system of max-plus linear equations
• Quantitative simulations by matrices
• The equation \(A \otimes x = B \otimes y\) over \((\max,+)\)
• Iteration algorithm for solving \(Ax = b\) in max--min algebra
• Hard problems in max-algebra, control theory, hypergraphs and other areas
• Log-Barrier Interior Point Methods Are Not Strongly Polynomial
• Weak dual residuations applied to tropical linear equations
• On two-sided max-linear equations
• On the solvability of homogeneous two-sided systems in max-algebra
• A note on a paper by E. Khorram and A. Ghodousian
• Optimization problems under (max, min)-linear equations and/or inequality constraints
• On max-min linear inequalities and coalitional resource games with sharable resources
• Tropical polyhedra are equivalent to mean payoff games
• Exponential behaviour of the Butkovič-Zimmermann algorithm for solving two-sided linear systems in max-algebra
• On the solution of a two-sided vector equation in tropical algebra
• Complexity of solving tropical linear systems
• On max-plus two-sided linear systems whose solution sets are min-plus linear

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

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