Search

Max-plus algebra is an algebraic structure in which classical addition and multiplication are replaced by maximum and addition, respectively. We say that the columns of a real matrix A are strongly independent if the max-plus linear system A ⊗ x = b has a unique solution for at least one real vector b. A square matrix A with strongly independent columns is called strongly regular. The investigation of the properties of regularity is important for applications. The values of vector or matrix inputs in practice are usually not exact numbers and they can be rather considered as values in some intervals. The present paper studies three versions of the regularity of matrices and interval matrices, namely, strong regularity, von Neumann regularity and Gondran-Minoux regularity. For each concept of regularity we will present equivalent conditions which can be verified in polynomial time. [ABSTRACT FROM AUTHOR]

Max-plus algebra is the similarity of the classical linear algebra with two binary operations, maximum and addition. The notation Ax = Bx, where A, B are given (interval) matrices, represents (interval) two-sided (max, plus)-linear system. For the solvability of Ax = Bx, there are some pseudopolynomial algorithms, but a polynomial algorithm is still waiting for an appearance. The paper deals with the analysis of solvability of two-sided (max, plus)-linear equations with inexact (interval) data. The purpose of the paper is to get efficient necessary and sufficient conditions for solvability of the interval systems using the property of the solution set of the non-interval system Ax = Bx. The main contribution of the paper is a transformation of weak versions of solvability to either subeigenvector problems or to non-interval two-sided (max, plus)-linear systems and obtaining the equivalent polynomially checked conditions for the strong versions of solvability.

Max-plus algebra is the similarity of the classical linear algebra with two binary operations, maximum and addition. The notation Ax = Bx, where A, B are given (interval) matrices, represents (interval) two-sided (max, plus)-linear system. For the solvability of Ax = Bx, there are some pseudopolynomial algorithms, but a polynomial algorithm is still waiting for an appearance. The paper deals with the analysis of solvability of two-sided (max, plus)-linear equations with inexact (interval) data. The purpose of the paper is to get efficient necessary and sufficient conditions for solvability of the interval systems using the property of the solution set of the non-interval system Ax = Bx. The main contribution of the paper is a transformation of weak versions of solvability to either subeigenvector problems or to non-interval two-sided (max, plus)-linear systems and obtaining the equivalent polynomially checked conditions for the strong versions of solvability. [ABSTRACT FROM AUTHOR]