The level set method for the two-sided max-plus eigenproblem
From MaRDI portal
Abstract: We consider the max-plus analogue of the eigenproblem for matrix pencils Ax=lambda Bx. We show that the spectrum of (A,B) (i.e., the set of possible values of lambda), which is a finite union of intervals, can be computed in pseudo-polynomial number of operations, by a (pseudo-polynomial) number of calls to an oracle that computes the value of a mean payoff game. The proof relies on the introduction of a spectral function, which we interpret in terms of the least Chebyshev distance between Ax and lambda Bx. The spectrum is obtained as the zero level set of this function.
Recommendations
Cites work
- scientific article; zbMATH DE number 193132 (Why is no real title available?)
- scientific article; zbMATH DE number 627763 (Why is no real title available?)
- scientific article; zbMATH DE number 1012624 (Why is no real title available?)
- scientific article; zbMATH DE number 2221678 (Why is no real title available?)
- scientific article; zbMATH DE number 2221682 (Why is no real title available?)
- A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
- A constructive fixed point theorem for min-max functions
- A generalized eigenvalue problem in the max algebra
- A method to find all solutions of a system of multivariate polynomial equalities and inequalities in the max algebra
- An algorithm for exact bounds on the time separation of events in concurrent systems
- Asymptotics of the Perron eigenvalue and eigenvector using max-algebra
- Best approximation in max-plus semimodules
- Convexity and log convexity for the spectral radius
- Cyclic projectors and separation theorems in idempotent convex geometry
- Eigenvalues of dynamic max-min systems
- Generalisation of the Perron-Frobenius theory to matrix pencils
- Idempotent functional analysis: An algebraic approach
- Max-algebra: The linear algebra of combinatorics?
- Max-linear systems. Theory and algorithms.
- Min-max functions
- Minimax algebra
- Multiorder, Kleene stars and cyclic projectors in the geometry of max cones
- On the problem \(Ax= \lambda Bx\) in max algebra: Every system of intervals is a spectrum
- Perturbation of eigenvalues of matrix pencils and the optimal assignment problem
- Scheduling with AND/OR Precedence Constraints
- Stochastic Games with Perfect Information and Time Average Payoff
- The complexity of mean payoff games on graphs
- The duality theorem for min-max functions
- The equation \(A \otimes x = B \otimes y\) over \((\max,+)\)
- The tropical analogue of polar cones
- Tropical convexity
- Tropical linear-fractional programming and parametric mean payoff games
- Tropical polar cones, hypergraph transversals, and mean payoff games
- Tropical polyhedra are equivalent to mean payoff games
- Z-Pencils
Cited in
(13)- On tropical fractional linear programming
- A convergent hierarchy of non-linear eigenproblems to compute the joint spectral radius of nonnegative matrices
- Tropical Fourier-Motzkin elimination, with an application to real-time verification
- Weakly linear systems for matrices over the max-plus quantale
- On max-plus linear dynamical system theory: the regulation problem
- Weak dual residuations applied to tropical linear equations
- Matrix representation of formal polynomials over max-plus algebra
- Eigenvalue methods for sparse tropical polynomial systems
- Analysis and control of max-plus linear discrete-event systems: an introduction
- On the problem \(Ax= \lambda Bx\) in max algebra: Every system of intervals is a spectrum
- On special cases of the generalized max-plus eigenproblem
- A basis theorem for a class of max-plus eigenproblems.
- On the continuity of the generalized spectral radius in max algebra
This page was built for publication: The level set method for the two-sided max-plus eigenproblem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2393147)
