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

DOI10.1016/J.DAM.2005.09.008MaRDI QIDQ2489939zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• scientific article; zbMATH DE number 5773726
• 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

Cites work

• scientific article; zbMATH DE number 2185206 (Why is no real title available?)
• scientific article; zbMATH DE number 3869093 (Why is no real title available?)
• scientific article; zbMATH DE number 627763 (Why is no real title available?)
• scientific article; zbMATH DE number 1163656 (Why is no real title available?)
• scientific article; zbMATH DE number 1516305 (Why is no real title available?)
• Linear and combinatorial optimization in ordered algebraic structures
• The equation \(A \otimes x = B \otimes y\) over \((\max,+)\)

Cited in

(29)

• A uniform synchronization problem over max-plus algebra
• AE solutions to two-sided interval linear systems over max-plus algebra
• scientific article; zbMATH DE number 5773726 (Why is no real title available?)
• scientific article; zbMATH DE number 1538845 (Why is no real title available?)
• 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
• Abstract tropical linear programming
• Idempotent and tropical mathematics; complexity of algorithms and interval analysis
• 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,+)\)
• Hard problems in max-algebra, control theory, hypergraphs and other areas
• Iteration algorithm for solving Ax = b in max--min algebra
• Weak dual residuations applied to tropical linear equations
• Log-Barrier Interior Point Methods Are Not Strongly Polynomial
• On two-sided max-linear equations
• A note on a paper by E. Khorram and A. Ghodousian
• On the solvability of homogeneous two-sided systems in max-algebra
• 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)