Max Algebra and the Linear Assignment Problem

Max-algebra, where the classical arithmetic operations of addition and multiplication are replaced by a+b:=max(a, b) and a+b:=a+b offers an attractive way for modelling discrete event systems and optimization problems in production and transportation. Moreover, it shows a strong similarity to classical linear algebra: for instance, it allows a consideration of linear equation systems and the eigenvalue problem. The max-algebraic permanent of a matrix A corresponds to the maximum value of the classical linear assignment problem with cost matrix A. The analogue of van der Waerden's conjecture in max-algebra is proved. Moreover the role of the linear assignment problem in max-algebra is elaborated, in particular with respect to the uniqueness of solutions of linear equation systems, regularity of matrices and the minimal-dimensional realisation of discrete event systems. Further, the eigenvalue problem in max-algebra is discussed. It is intimately related to the best principal submatrix problem which is finally investigated: Given an integer k, 1less than or equal tokless than or equal ton, find a (kxk) principal submatrix of the given (nxn) matrix which yields among all principal submatrices of the same size the maximum (minimum) value for an assignment. For k=1,2,...,n, the maximum assignment problem values of the principal (kxk) submatrices are the coefficients of the max-algebraic characteristic polynomial of the matrix for A. This problem can be used to model job rotations.