Max algebra and the linear assignment problem
详细信息 查看全文
- 作者：Rainer E. Burkard and Peter Butkovic
- 关键词：max ; algebra ; assignment problem ; permanent ; regular matrix ; discrete event system ; characteristic maxpolynomial ; best principal submatrix assignment problem ; job rotation problem
- 刊名：Mathematical Programming
- 出版年：2003
- 出版时间：September 2003
- 年：2003
- 卷：98
- 期：1-3
- 页码：415-429
- 全文大小：171 KB
- 刊物类别：Mathematics and Statistics
- 刊物主题：Mathematics
Calculus of Variations and Optimal Control
Mathematics of Computing
Numerical Analysis
Combinatorics
Mathematical and Computational Physics
Mathematical Methods in Physics - 出版者：Springer Berlin / Heidelberg
- ISSN：1436-4646
文摘
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.