Max Algebra and the Linear Assignment Problem

RE Burkard, Peter Butkovic

Research output: Contribution to journalArticle

16 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)415-429
Number of pages15
JournalMathematical Programming
Issue number1-3
Publication statusPublished - 1 Sept 2003


  • discrete event system
  • permanent
  • assignment problem
  • max-algebra
  • best principal submatrix assignment problem
  • job rotation problem
  • regular matrix
  • characteristic maxpolynomial


Dive into the research topics of 'Max Algebra and the Linear Assignment Problem'. Together they form a unique fingerprint.

Cite this