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

Vincent D. Blondel, Stéphane Gaubert, John N. TsitsiklisIEEE Trans. Automatic Control 2000 · OpenReview

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 the 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.
BibTeX
@article{blondel2000approximating,
  author = {Vincent D. Blondel and Stéphane Gaubert and John N. Tsitsiklis},
  title = {{Approximating the spectral radius of sets of matrices in the max-algebra is NP-hard}},
  journal = {IEEE Trans. Automatic Control},
  year = {2000},
  url = {https://openreview.net/forum?id=y6e8g5ZR5Z},
}

Loading related content...

Figure