2000 • Journal Article
Approximating the spectral radius of sets of matrices in the max-algebra is NP-Hard
Authors:
Blondel, Vincent ,
Gaubert, S,
Tsitsiklis, John
Published in:
IEEE Transactions on Automatic Control
Volume: 45 • Number: 9 • Pages: 1762-1765
The lower and average spectral radii measure, respectively, the minimal and average growth rates of long products of matrices taken From a finite set. The logarithm of the average spectral radius is traditionally called Lyapunov exponent. When one performs these products in the max-algebra, we obtain quantities that measure the performance of Discrete Event Systems. We show that approximating the lower and average max-algebraic spectral radii is NP-hard.