Max-algebra: The linear algebra of combinatorics?

DOI10.1016/S0024-3795(02)00655-9zbMath1022.15017OpenAlexW2107551402MaRDI QIDQ1873718

Publication date: 27 May 2003

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0024-3795(02)00655-9

zbMATH Keywords

eigenvalue digraph eigenvectors combinatorial problems permutation set covering problem permanent assignment problem combinatorial optimization problems max-algebra directed cycle matrix scaling solvability problem best principal submatrix longest-distances maximal cycle mean

Mathematics Subject Classification ID

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

Related Items

TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES, Rank functions of tropical matrices, On tropical supereigenvectors, Closure of the simple image set of linear mapping interval max-plus, Perron-Frobenius theorem for hypermatrices in the max algebra, Weakly linear systems for matrices over the max-plus quantale, Orthogonal complements and extending orthogonal subsets of semimodules, Max algebraic powers of irreducible matrices in the periodic regime: an application of cyclic classes, Elements of tropical linear algebra, Carathéodory, Helly and the others in the max-plus world, THE FINITE BASIS PROBLEM FOR THE MONOID OF TWO-BY-TWO UPPER TRIANGULAR TROPICAL MATRICES, Group algebra of characteristic 1 and invariant distances over a finite group, Unnamed Item, A congruence on the semiring of normal tropical matrices, On the least distributive lattice congruence on a semiring with a semilattice additive reduct, On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product, The level set method for the two-sided max-plus eigenproblem, A note on tropical triangles in the plane, Dimensional formulas of semilinear subspaces over semirings, Max-plus definite matrix closures and their eigenspaces, Generators, extremals and bases of max cones, Orthogonality for \((0, -1)\) tropical normal matrices, A cubic time algorithm for finding the principal solution to Sylvester matrix equations over (max, +), Fiedler-Pták scaling in max algebra, The cardinality of bases in semilinear spaces over commutative semirings, Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria, Dominant matrices and max algebra, Computing the vertices of tropical polyhedra using directed hypergraphs, Solving linear equations over maxmin-\(\omega\) systems, Bases in semilinear spaces over join-semirings, Analysis of linear systems over idempotent semifields, Bases in semilinear spaces over zerosumfree semirings, On the complexity of Boolean matrix ranks, Two cores of a nonnegative matrix, Note on cardinality of bases in semilinear spaces over zerosumfree semirings, On integer images of max-plus linear mappings, Supertropical algebra, Quasi-Euclidean classification of alcoved convex polyhedra, Inclines and incline matrices: A survey., Algorithms for approximate subtropical matrix factorization, Dependence of supertropical eigenspaces, The tropical matrix groups with symmetric idempotents, A note on tropical linear and integer programs, Max Plus Algebra, Optimization and Game Theory, Idempotent definite closures of matrices, Matrices commuting with a given normal tropical matrix, Supertropical SL_n, Note on the free sets and free subsemimodules in semimodules, Compromise approach for predictive control of timed event graphs with specifications defined by P-time event graphs, Finding a bounded mixed-integer solution to a system of dual network inequalities, Permuted max-algebraic eigenvector problem is \(NP\)-complete, Standard orthogonal vectors in semilinear spaces and their applications, Tropical compound matrix identities, On the continuity of the generalized spectral radius in max algebra, A note on the parity assignment problem, How many Boolean polynomials are irreducible?, On pseudo-inverses of matrices and their characteristic polynomials in supertropical algebra, On the problem Ax=\lambda Bx in max algebra: every system of intervals is a spectrum, Multiplicative structure of \(2\times 2\) tropical matrices, Inequalities for Gondran-Minoux rank and idempotent semirings, \(P_{\max}^1\) and \(S_{\max}\) properties and asymptotic stability in the max algebra, Matrix Invariants over Semirings, Sparsity in max-plus algebra and systems, Tropical totally positive matrices, The bideterminants of matrices over semirings, A survey on fuzzy relational equations. I: Classification and solvability, Orderings on semirings and completely positive matrices, Inequalities for the spectral radius of non-negative functions, On the integer max-linear programming problem, Equational theories of upper triangular tropical matrix semigroups, Solving linear systems over idempotent semifields through \(LU\)-factorization, Tropical Arithmetic and Matrix Algebra, The DJL Conjecture for CP Matrices over Special Inclines, On generalized inverses of \(m \times n\) matrices over a pseudoring, Optimal assignments with supervisions, On tropical Kleene star matrices and alcoved polytopes, On the groups associated with a tropical \(n\times n\) matrix, An informal overview of triples and systems, A short note on the weighted sub-partition mean of integers, On visualization scaling, subeigenvectors and Kleene stars in max algebra, CSR expansions of matrix powers in max algebra, Multi-dimensional vector assignment problems, Extension of free sets over commutative semirings, Completely positive matrices over Boolean algebras and their CP-rank, Z-matrix equations in max-algebra, nonnegative linear algebra and other semirings, Non-surjective linear transformations of tropical matrices preserving the cyclicity index

Cites Work