Max algebra and the linear assignment problem

Max-algebra, where the classical arithmetic operations of addition and multiplication are replaced by ab:=max(a, b) and ab:=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, 1kn, find a (k×k) principal submatrix of the given (n×n) 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 (k×k) submatrices are the coefficients of the max-algebraic characteristic polynomial of the matrix for A. This problem can be used to model job rotations.This research has been supported by the Engineering and Physical Sciences Research Council grant RRAH07961 ``Unresolved Variants of the Assignment Problem' and by the Spezialforschungsbereich F 003 ``Optimierung und Kontrolle', Projektbereich Diskrete Optimierung.Mathematics Subject Classification (2000):90C27, 15A15, 93C83