Max algebra and the linear assignment problem

Max algebra and the linear assignment problem

0.00 Avg rating0 Votes
Article ID: iaor20051089
Country: Germany
Volume: 98
Issue: 1/3
Start Page Number: 415
End Page Number: 429
Publication Date: Jan 2003
Journal: Mathematical Programming
Authors: ,
Abstract:

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, 1 ≤ kn, find a (k × n) 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.

Reviews

Required fields are marked *. Your email address will not be published.