Max-linear Systems: Theory and Algorithms

DOI10.1007/978-1-84996-299-5zbMath1202.15032OpenAlexW341186930WikidataQ30052845 ScholiaQ30052845MaRDI QIDQ3565227

Peter Butkovic

Publication date: 3 June 2010

Published in: Springer Monographs in Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-1-84996-299-5

zbMATH Keywords

monographcombinatoricsalgorithmeigenvaluescombinatorial optimizationeigenvectorsfactorization of polynomialsspectral propertiessemiringslinear independenceirreducible matricesalgorithmic problemsmax-plus linear algebraGondran-Minoux regularitymatrix regularitymax-algebraicmax-algebraic polynomialsmax-linear programs

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Linear programming (90C05) Combinatorial optimization (90C27) Linear inequalities of matrices (15A39) Eigenvalues, singular values, and eigenvectors (15A18) Polynomials in real and complex fields: factorization (12D05) Semirings (16Y60) Vector spaces, linear dependence, rank, lineability (15A03) Linear equations (linear algebraic aspects) (15A06) Research exposition (monographs, survey articles) pertaining to linear algebra (15-02) Max-plus and related algebras (15A80)

Related Items

Closure of the simple image set of linear mapping interval max-plus, Surjective linear transformations of tropical matrices preserving transitive closures, On the tightness of bounds for transients of weak CSR expansions and periodicity transients of critical rows and columns of tropical matrix powers, Tropical Time Series, Iterated-Sums Signatures, and Quasisymmetric Functions, Tropical Vandermonde matrices, On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product, Tropical pseudolinear and pseudoquadratic optimization as parametric mean-payoff games, Dynamics of products of matrices in max algebra, Regularity of interval max-plus matrices, Relatively maximal perturbation bounds for global robustness of max‐plus linear systems, Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria, Certain congruences on the semiring of normal tropical matrices, Approximately global optimal control for max-plus linear systems and its application on load distribution, Timetable compression using max-plus automata applied to large railway networks, Tropical medians by transportation, Presentations of transversal valuated matroids, Combination of t-norms and their conorms, Derivations of some classes of additively idempotent semirings, On the 2-rainbow independent domination numbers of some graphs, On the solution of a two-sided vector equation in tropical algebra, Monomial Tropical Cones for Multicriteria Optimization, Convergent Hahn series and tropical geometry of higher rank, Solving linear equations over maxmin-\(\omega\) systems, Diagnosing Hybrid Dynamical Systems Using Max-Plus Algebraic Methods, Tropical Geometry, Derivations of skew Ore polynomial semirings, Unnamed Item, A note on the paper ‘Ultra discrete permanent and the consistency of max plus linear equations’, A Max-Plus algebra approach for generating a non-delay schedule, Geometric Quantifier Elimination Heuristics for Automatically Generating Octagonal and Max-plus Invariants, Tropical Cryptography, Matrix representation of formal polynomials over max-plus algebra, Regular D-classes of the semigroup of n x n tropical matrices, Approximating the volume of tropical polytopes is difficult, A note on resolving the inconsistency of one-sided max-plus linear equations, Derivations of polynomial semirings, Matrix Analysis and Omega Calculus, A bound for the rank-one transient of inhomogeneous matrix products in special case, Tropical cryptography II: Extensions by homomorphisms, On tropical Kleene star matrices and alcoved polytopes, The characterizations of irreducible matrices with proper supereigenvectors, On the numerical range in tropical algebra, Unifying Matrix Stability Concepts with a View to Applications, Comparison of max-plus automata and joint spectral radius of tropical matrices, A multidimensional tropical optimization problem with a non-linear objective function and linear constraints, Derivatives of triangular, Toeplitz, circulant matrices and of matrices of other forms over semirings, A min-plus analogue of the Jordan canonical form associated with the basis of the generalized eigenspace, Topological Entropy of Surface Braids and Maximally Efficient Mixing, Parametric Shortest-Path Algorithms via Tropical Geometry, Morphological Perceptrons: Geometry and Training Algorithms, Interval multi-linear systems for tensors in the max-plus algebra and their application in solving the job shop problem, Minimizing maximum lateness in two-stage projects by tropical optimization, Algebraic solutions of tropical optimization problems, Rank functions of tropical matrices, On scaling to an integer matrix and graphs with integer weighted cycles, On tropical supereigenvectors, Non-archimedean valuations of eigenvalues of matrix polynomials, A uniform synchronization problem over max-plus algebra, Weighted digraphs and tropical cones, A MAX-plus model of ribosome dynamics during mRNA translation, Second main theorem in the tropical projective space, \(\mathbf{X}\)-simple image eigencones of tropical matrices, The tropical commuting variety, Explicit formulae for the greatest least-squares and minimum norm \(g\)-inverses and the unique group inverse of matrices over commutative residuated dioids, Semigroup identities of tropical matrix semigroups of maximal rank, Tropical matrix groups, Pure dimension and projectivity of tropical polytopes, Strong solvability of interval max-plus systems and applications to optimal control, Towards robust predictive fault-tolerant control for a battery assembly system, Complete algebraic solution of multidimensional optimization problems in tropical semifield, Tropical differential equations, A congruence on the semiring of normal tropical matrices, Induced representations and hypercomplex numbers, Lower spectral radius and spectral mapping theorem for suprema preserving mappings, An extremal property of the eigenvalue of irreducible matrices in idempotent algebra and solution of the Rawls location problem, Number of common roots and resultant of two tropical univariate polynomials, Basic \(r\)-symmetric tropical polynomials, Interval strong solutions of interval systems of max-plus linear equations, Tropical linear algebra with the Łukasiewicz t-norm, The spectra of irreducible matrices over completed idempotent semifields, Fiedler-Pták scaling in max algebra, Generalized spectral radius and its max algebra version, Supertropical quadratic forms. I., Pairwise ranking: choice of method can produce arbitrarily different rank order, Universal algorithms for solving the matrix Bellman equations over semirings, The weak robustness of interval matrices in max-plus algebra, The generators of the solution space for a system of inequalities, On tropical eigenvalues of tridiagonal Toeplitz matrices, Weak CSR expansions and transience bounds in max-plus algebra, On a tropical dual Nullstellensatz, The analytic hierarchy process, max algebra and multi-objective optimisation, Bounds on the generalized and the joint spectral radius of Hadamard products of bounded sets of positive operators on sequence spaces, Filter-embedding semiring fusion for programming with MapReduce, Computing the vertices of tropical polyhedra using directed hypergraphs, Tropical optimization problems with application to project scheduling with minimum makespan, Green's \(\mathcal J\)-order and the rank of tropical matrices., Complexity of solving tropical linear systems, The robustness of interval fuzzy matrices, On integer eigenvectors and subeigenvectors in the max-plus algebra, Lifespan in a primitive Boolean linear dynamical system, Identities in upper triangular tropical matrix semigroups and the bicyclic monoid, Tropical linear-fractional programming and parametric mean payoff games, On integer images of max-plus linear mappings, Using tropical optimization to solve minimax location problems with a rectilinear metric on the line, Max-linear models on directed acyclic graphs, On commuting matrices in max algebra and in classical nonnegative algebra, On two-sided max-linear equations, The tropical matrix groups with symmetric idempotents, Tropical plactic algebra, the cloaktic monoid, and semigroup representations, A note on tropical linear and integer programs, Symmetric polynomials in tropical algebra semirings, Tropical principal component analysis and its application to phylogenetics, Matrices commuting with a given normal tropical matrix, Max-plus singular values, Tropical spectrahedra, A tropical isoperimetric inequality, Tropical effective primary and dual Nullstellensätze, Resultants over commutative idempotent semirings. I: Algebraic aspect, Dynamical systems on weighted lattices: general theory, Reachability of eigenspaces for interval circulant matrices in max-algebra, Compromise approach for predictive control of timed event graphs with specifications defined by P-time event graphs, Uniform boundedness principle for nonlinear operators on cones of functions, A polynomial algorithm for solving system of inequalities in max-plus algebra, Monotone linear transformations on matrices over semirings, Exploring the complexity of the integer image problem in the \(\max\)-algebra, Tropical compound matrix identities, Steady states in the scheduling of discrete-time systems, Max-algebraic attraction cones of nonnegative irreducible matrices, On sets of eigenvalues of matrices with prescribed row sums and prescribed graph, On \(2 \times 2\) tropical commuting matrices, Spectral inequalities for nonnegative tensors and their tropical analogues, Analysis of a key exchange protocol based on tropical matrix algebra, Goldbach's conjecture in max-algebra, Direct solution to constrained tropical optimization problems with application to project scheduling, Rank-one approximation of positive matrices based on methods of tropical mathematics, AE and EA robustness of interval circulant matrices in max-product algebra, \((K,L)\)-eigenvectors in max-min algebra, Tropical totally positive matrices, Tropical implementation of the analytical hierarchy process decision method, Subeigenvectors and supereigenvectors of fuzzy matrices, An optimization problem on the image set of a (max, min) fuzzy operator, Algebraic solution of a problem of optimal project scheduling in project management, Ultra discrete permanent and the consistency of max plus linear equations, Generalizations of bounds on the index of convergence to weighted digraphs, On the integer max-linear programming problem, Solving linear systems over idempotent semifields through \(LU\)-factorization, On the spectrum in max algebra, Convexity of tropical polytopes, On generalized inverses of \(m \times n\) matrices over a pseudoring, Nonlinear small-gain theorems for input-to-state stability of infinite interconnections, Enumerating Polytropes, Interval robustness of (interval) max-plus matrices, Loop-checking and the uniform word problem for join-semilattices with an inflationary endomorphism, On the Bonsall cone spectral radius and the approximate point spectrum, Semigroups of max-plus linear operators, Characterization of tropical projective quadratic plane curves in terms of the eigenvalue problem, Weakly linear systems for matrices over the max-plus quantale, The non-positive circuit weight problem in parametric graphs: a solution based on dioid theory, Idempotent and tropical mathematics; complexity of algorithms and interval analysis, A feasible schedule for parallel assembly tasks in flexible manufacturing systems, On common eigenvectors for semigroups of matrices in tropical and traditional linear algebra, An improved algorithm for finding the generators of the solution space for \(A\otimes \mathbf{x}\ge \mathbf{x} \), Unnamed Item, Determinants and limit systems in some idempotent and non-associative algebraic structure, The level set method for the two-sided max-plus eigenproblem, Eigenproblem for optimal-node matrices in max-plus algebra, Algebraic solution of tropical optimization problems via matrix sparsification with application to scheduling, Computing the sequence of \(k\)-cardinality assignments, Adaptive thresholding technique for solving optimization problems on attainable sets of (max, min)-linear systems, Tropical Gaussians: a brief survey, On an algebraic solution of the Rawls location problem in the plane with rectilinear metric, Solution of a tropical optimization problem with linear constraints, Extreme rays of the \(\ell^\infty\)-nearest ultrametric tropical polytope, Orthogonality for \((0, -1)\) tropical normal matrices, A cubic time algorithm for finding the principal solution to Sylvester matrix equations over (max, +), Generic uniqueness of the bias vector of finite zero-sum stochastic games with perfect information, Solving generic nonarchimedean semidefinite programs using stochastic game algorithms, Analysis and control of max-plus linear discrete-event systems: an introduction, Perron-Frobenius theory for some classes of nonnegative tensors in the max algebra, Using tropical optimization techniques in bi-criteria decision problems, Local and global robustness with \(q\)-step delay for max-plus linear systems, Geometry and algorithms for upper triangular tropical matrix identities, A characterization of bases of tropical kernels in terms of Cramer's rule, Extremality criteria for the supereigenvector space in max-plus algebra, Abstract tropical linear programming, Toward a sparsity theory on weighted lattices, Tropical Carathéodory with matroids, On the numerical ranges of matrices in max algebra, Tropical representations and identities of the stylic monoid, Max-Plus Algebraic Statistical Leverage Scores, An algebraic expression of the number partitioning problem, Algebraic solution to optimal scheduling problems taking into account the scheduled start time of jobs in projects, Face monoid actions and tropical hyperplane arrangements, Normal tropical \((0,-1)\)-matrices and their orthogonal sets, Towards a health-aware fault tolerant control of complex systems: a vehicle fleet case, \(\mathcal{K}\)-formal concept analysis as linear algebra over idempotent semifields, Two cores of a nonnegative matrix, Global optimization for max-plus linear systems and applications in distributed systems, Exact rings and semirings., The robustness of interval matrices in max-plus algebra, Tropical bounds for eigenvalues of matrices, Comparison of the quasi-inverses of the Kronecker sum and product of matrices over complete commutative dioids with applications, Isocanted alcoved polytopes., Modifying the tropical version of Stickel's key exchange protocol., Complete solution of tropical vector inequalities using matrix sparsification., Optimization problem under two-sided \((\max,+)/(\min,+)\) inequality constraints., On the vectors associated with the roots of max-plus characteristic polynomials., Duality of optimization problems with generalized fuzzy relation equation and inequality constraints, Algorithms for approximate subtropical matrix factorization, Semigroup identities in the monoid of triangular tropical matrices., Bisimulations for weighted automata over an additively idempotent semiring, Tropical Ehrhart theory and tropical volume, New bounds on the periodicity transient of the powers of a tropical matrix: using cyclicity and factor rank, Max Plus Algebra, Optimization and Game Theory, Recursive max-linear models with propagating noise, Matrix roots in the max-plus algebra, Polytropes and tropical eigenspaces: cones of linearity, MAX algebraic complementary basic matrices, On the problem Ax=\lambda Bx in max algebra: every system of intervals is a spectrum, Unnamed Item, Max-plus linear inverse problems: 2-norm regression and system identification of max-plus linear dynamical systems with Gaussian noise, Tolerance types of interval eigenvectors in max-plus algebra, Solving a tropical optimization problem with application to optimal scheduling, Sparsity in max-plus algebra and systems, The Markov chain tree theorem in commutative semirings and the state reduction algorithm in commutative semifields, Extremal properties of tropical eigenvalues and solutions to tropical optimization problems, Polynomial threshold functions and Boolean threshold circuits, On the rank-one approximation of positive matrices using tropical optimization methods, Distances on the tropical line determined by two points, Interval max-plus fault-tolerant control under resource conflicts and redundancies: application to the seat assembly, On Special Cases of the Generalized Max-Plus Eigenproblem, Tropical planar networks, Sparse approximate solutions to max-plus equations, Max-plus automata, Reachability of eigenspaces for interval matrices in max-min algebra, Polynomial convolutions in max-plus algebra, On the groups associated with a tropical \(n\times n\) matrix, \(X^{A E}\) and \(X^{E A}\) robustness of max-min matrices, CSR expansions of matrix powers in max algebra, Max-plus steady states in discrete event dynamic systems with inexact data, Semigroup identities of supertropical matrices, Max-Balanced Hungarian Scalings, Min-plus eigenvalue of tridiagonal matrices in terms of the ultradiscrete Toda equation, Design of a Predictive Fault-Tolerant Control for the Battery Assembly Station, The ultimate rank of tropical matrices, Extremals of the supereigenvector cone in max algebra: a combinatorial description, A strongly polynomial method for solving integer max-linear optimization problems in a generic case, Z-matrix equations in max-algebra, nonnegative linear algebra and other semirings, Fast distance multiplication of unit-Monge matrices, Lossy gossip and composition of metrics, Complexity of tropical and MIN-plus linear prevarieties, Conditional independence in max-linear Bayesian networks