Approximating the spectral radius of sets of matrices in the max-algebra is NP-hard

DOI10.1109/9.880644zbMath0990.93073OpenAlexW2133763708MaRDI QIDQ2730242

Stéphane Gaubert, Blondel, Vincent D., John N. Tsitsiklis

Publication date: 5 August 2001

Published in: IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/22c3c933e2667b0db3a0532f9c6acb6ce30e93aa

zbMATH Keywords

computational complexityspectral radiusNP-hardmax-plus algebradiscrete event systems

Mathematics Subject Classification ID

Discrete event control/observation systems (93C65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity and performance of numerical algorithms (65Y20)

Related Items

Stochastic stability in Max-Product and Max-Plus systems with Markovian jumps ⋮ Generalized spectral radius and its max algebra version ⋮ Lower and upper bounds for the largest Lyapunov exponent of matrices ⋮ Generalized Markov-Bernstein inequalities and stability of dynamical systems ⋮ Exact computation of joint spectral characteristics of linear operators ⋮ Computing the average parallelism in trace monoids. ⋮ Algorithms for approximate subtropical matrix factorization ⋮ APPROXIMATING THE MEAN SPEEDUP IN TRACE MONOIDS ⋮ Uniform and Bernoulli measures on the boundary of trace monoids ⋮ A central limit theorem for stochastic recursive sequences of topical operators ⋮ A survey of computational complexity results in systems and control ⋮ Tail asymptotics for discrete event systems ⋮ On the max version of the generalized spectral radius theorem ⋮ Extremal \(L_p\)-norms of linear operators and self-similar functions ⋮ On the continuity of the generalized spectral radius in max algebra ⋮ Approximability and Non-approximability Results in Computing the Mean Speedup of Trace Monoids ⋮ Invariant Polytopes of Sets of Matrices with Application to Regularity of Wavelets and Subdivisions ⋮ Continuity of the generalized spectral radius in max algebra ⋮ Comparison of max-plus automata and joint spectral radius of tropical matrices ⋮ On the average Cartier-Foata height of traces