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

Abstract

An algorithm for solving mxn systems of (max,+)-linear equations is presented. The systems have variables on both sides of the equations.

After O(m^4 n^4) iterations the algorithm either finds a solution of the system or finds out that no solution exists. Each iteration needs O(mn) operations so that the complexity of the presented algorithm is O(m^5n^5).

Keywords

• strongly
• polynomial
• algorithm
• solving
• two-sided
• linear
• systems
• max-algebra