Max-algebra: the linear algebra of combinatorics?

Let a circle plus b = max(a,b), a circle times b = a + b for a, b is an element of (R) over bar:= R boolean OR {-infinity}. By max-algebra we understand the analogue of linear algebra developed for the pair of operations (circle plus, circle times) extended to matrices and vectors. Max-algebra, which has been studied for more than 40 years, is an attractive way of describing a class of nonlinear problems appearing for instance in machine-scheduling, information technology and discrete-event dynamic systems. This paper focuses on presenting a number of links between basic max-algebraic problems like systems of linear equations, eigenvalue-eigenvector problem, linear independence, regularity and characteristic polynomial on one hand and combinatorial or combinatorial optimisation problems on the other hand. This indicates that max-algebra may be regarded as a linear-algebraic encoding of a class of combinatorial problems. The paper is intended for wider readership including researchers not familiar with max-algebra. (C) 2003 Elsevier Science Inc. All rights reserved.