TY - JOUR

T1 - Max-algebra: the linear algebra of combinatorics?

AU - Butkovic, Peter

PY - 2003/7/1

Y1 - 2003/7/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0038057772&partnerID=8YFLogxK

U2 - 10.1016/S0024-3795(02)00655-9

DO - 10.1016/S0024-3795(02)00655-9

M3 - Article

VL - 367

SP - 313

EP - 335

JO - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

ER -