Max-algebra: The linear algebra of combinatorics? (Q1873718): Difference between revisions

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.