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

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

doi:10.1109/9.880644

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

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

University of Louvain
Massachusetts Institute of Technology

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

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.

langue originale	Anglais
Pages (de - à)	1762-1765
Nombre de pages	4
journal	IEEE Transactions on Automatic Control
Volume	45
Numéro de publication	9
Les DOIs	https://doi.org/10.1109/9.880644
état	Publié - 1 sept. 2000

Accès au document

10.1109/9.880644

Contient cette citation

@article{359bae8205234e328d14d4cec4dfbd4d,

title = "Approximating the spectral radius of sets of matrices in the max-algebra is NP-hard",

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.",

author = "Blondel, \{Vincent D.\} and St{\'e}phane Gaubert and Tsitsiklis, \{John N.\}",

year = "2000",

month = sep,

day = "1",

doi = "10.1109/9.880644",

language = "English",

volume = "45",

pages = "1762--1765",

journal = "IEEE Transactions on Automatic Control",

issn = "0018-9286",

number = "9",

}

TY - JOUR

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

AU - Blondel, Vincent D.

AU - Gaubert, Stéphane

AU - Tsitsiklis, John N.

PY - 2000/9/1

Y1 - 2000/9/1

N2 - 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.

AB - 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.

U2 - 10.1109/9.880644

DO - 10.1109/9.880644

M3 - Article

AN - SCOPUS:0034262644

SN - 0018-9286

VL - 45

SP - 1762

EP - 1765

JO - IEEE Transactions on Automatic Control

JF - IEEE Transactions on Automatic Control

IS - 9

ER -

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

Résumé

Accès au document

Empreinte digitale

Contient cette citation