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 -