Max-algebra: The linear algebra of combinatorics? (English) Zbl 1022.15017

The paper deals with the relationship between basic max-algebraic problems and combinatorial or combinatorial optimization problems.
By max-algebra the author understands the analogue of linear algebra developed for the pair of operations \((\oplus, \otimes)\) extended to matrices and vectors formally in the same way as in linear algebra.
The author presents an overview of results which demonstrate strong links between basic max-algebraic problems and combinatorial or combinatorial optimization problems. Examples of such combinatorial problems are: the set covering problem, which in max-algebra is the solvability problem of a linear system; the minimal set covering problem, that in max-algebra is the unique solvability of a linear system; existence of a directed cycle, which is related to the strong regularity of a matrix; existence of an even directed cycle (regularity of a matrix); maximal cycle mean (eigenvalue); longest-distances (eigenvectors); and best principal submatrix (coefficients of a characteristic polynomial).
Finally, some results are related to matrix scaling which enable the author to formulate a link between combinatorial problems so different as the assignment problem and the longest-distances problem.


15A30 Algebraic systems of matrices
15A18 Eigenvalues, singular values, and eigenvectors
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A15 Determinants, permanents, traces, other special matrix functions
90C27 Combinatorial optimization
15A06 Linear equations (linear algebraic aspects)
Full Text: DOI


[1] Baccelli, F.L; Cohen, G; Olsder, G.-J; Quadrat, J.-P, Synchronization and linearity, (1992), John Wiley Chichester, New York
[2] Bapat, R.B; Raghavan, T.E.S, Nonnegative matrices and applications, (1997), Cambridge University Press London · Zbl 0879.15015
[3] Brualdi, R.A; Ryser, H, Combinatorial matrix theory, (1981), Cambridge University Press London
[4] R.E. Burkard, P. Butkovič, Finding all essential terms of a characteristic maxpolynomial, SFB Report No. 249, Institute of Mathematics, Graz University of Technology, 2002
[5] R.E. Burkard, E. Çela, Linear assignment problems and extensions, in: P.M. Pardalos, D.-Z. Du (Eds.), Handbook of Combinatorial Optimization, Supplement vol. A, Kluwer Academic Publishers, 1999, pp. 75-149 · Zbl 1253.90131
[6] Butkovič, P, Strong regularity of matrices–a survey of results, Discrete appl. math., 48, 45-68, (1994) · Zbl 0804.06017
[7] Butkovič, P, Regularity of matrices in MIN-algebra and its time-complexity, Discrete appl. math., 57, 121-132, (1995) · Zbl 0820.15003
[8] Butkovič, P, Simple image set of (MAX,+) linear mappings, Discrete appl. math., 105, 73-86, (2000) · Zbl 0976.15013
[9] P. Butkovič, On the coefficients of the max-algebraic characteristic polynomial and equation, in: Proceedings of the Workshop on Max-algebra, Symposium of the International Federation of Automatic Control, Prague, 2001
[10] Butkovič, P; Hevery, F, A condition for the strong regularity of matrices in the minimax algebra, Discrete appl. math., 11, 209-222, (1985) · Zbl 0602.90136
[11] Butkovič, P; Murfitt, L, Calculating essential terms of a characteristic maxpolynomial, Cejor, 8, 237-246, (2000) · Zbl 0982.90042
[12] J. Cochet-Terrasson, G. Cohen, S. Gaubert, M. McGettrick, J.-P. Quadrat, Numerical computation of spectral elements in max-plus algebra, in: IFAC Conference on System Structure and Control, 1998
[13] R.A. Cuninghame-Green, Minimax Algebra, Lecture Notes in Economics and Math. Systems, vol. 166, Springer, Berlin, 1979
[14] Cuninghame-Green, R.A, The characteristic maxpolynomial of a matrix, J. math. anal. appl., 95, 110-116, (1983) · Zbl 0526.90098
[15] R.A. Cuninghame-Green, Minimax algebra and applications, in: Advances in Imaging and Electron Physics, vol. 90, pp. 1-121, Academic Press, New York, 1995
[16] Fiedler, M; Pták, V, Diagonally dominant matrices, Czechoslovak math. J., 92, 420-433, (1967) · Zbl 0178.03402
[17] S. Gaubert, Théorie des systèmes linéaires dans les dioı̈des, Thèse, Ecole des Mines de Paris, 1992
[18] S. Gaubert et al., Algèbres Max-Plus et applications en informatique et automatique, 26ème école de printemps d’informatique théorique, Noirmoutier, 1998
[19] M. Gondran, Path algebra and algorithms, in: B. Roy (Ed.), Combinatorial programming: methods and applications (Proc. NATO Advanced Study Inst., Versailles, 1974) NATO Advanced Study Inst. Ser., Ser. C: Math. and Phys. Sci., 19, Reidel, Dordrecht, pp. 137-148, 1975
[20] M. Gondran, M. Minoux, L’indépendance linéaire dans les dioı̈des, Bulletin de la Direction Etudes et Recherches, EDF, Série C 1 67-90, 1978
[21] Gondran, M; Minoux, M, Linear algebra of dioı̈ds: a survey of recent results, Ann. discrete math., 19, 147-164, (1984) · Zbl 0568.08001
[22] Papadimitriou, C.H; Steiglitz, K, Combinatorial optimization-algorithms and complexity, (1998), Dover · Zbl 0944.90066
[23] Robertson, N; Seymour, P.D; Thomas, R, Permanents, Pfaffian orientations and even directed circuits, Ann. math., 150, 2, 929-975, (1999) · Zbl 0947.05066
[24] Schneider, H; Schneider, M.H, MAX-balancing weighted directed graphs and matrix scaling, Math. oper. res., 16, 1, 208-222, (1991) · Zbl 0729.90085
[25] Thomassen, C, Sign-nonsingular matrices and even cycles in directed graphs, Linear algebra appl., 75, 27-41, (1986) · Zbl 0589.05050
[26] K. Zimmermann, Extremálnı́ algebra, Výzkumná publikace Ekonomicko–matematické laboratoře při Ekonomickém ústavě ČSAV, 46, Praha, 1976 (in Czech)
[27] U. Zimmermann, Linear and Combinatorial Optimization in Ordered Algebraic Structures, in: Ann. Discrete Math., vol. 10, North-Holland, Amsterdam, 1981 · Zbl 0466.90045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.