Max-Algebra - the Linear Algebra of Combinatorics?

Let ⊕ = max(, ), ⊗ = + for . By max-algebra we understand the analogue of linear algebra developed for the pair of operations (⊕, ⊗) 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