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

Blondel, Vincent;Gaubert, S;Tsitsiklis, John
(2000) IEEE Transactions on Automatic Control — Vol. 45, n° 9, p. 1762-1765 (2000)

Files

No attached file found for this publication.

Details

Authors
Abstract
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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Blondel, V., Gaubert, S., & Tsitsiklis, J. (2000). Approximating the spectral radius of sets of matrices in the max-algebra is NP-Hard. IEEE Transactions on Automatic Control, 45(9), 1762-1765. https://doi.org/10.1109/9.880644 (Original work published 2000)