Milan Hladík. Complexity issues for the symmetric interval eigenvalue problem. Open Math., 13(1):157–164, 2015.
[PDF] [gzipped postscript] [postscript] [HTML]
We study the problem of computing the maximal and minimal possible eigenvalues of a symmetric matrix when the matrix entries vary within compact intervals. In particular, we focus on computational complexity of determining these extremal eigenvalues with some approximation error. Besides the classical absolute and relative approximation errors, which turn out not to be suitable for this problem, we adapt a less known one related to the relative error, and also propose a novel approximation error. We show in which error factors the problem is polynomially solvable and in which factors it becomes NP-hard.
@article{Hla2015b,
author = "Milan Hlad\'{\i}k",
title = "Complexity issues for the symmetric interval eigenvalue problem",
journal = "Open Math.",
fjournal = "Open Mathematics",
volume = "13",
number = "1",
pages = "157-164",
year = "2015",
doi = "10.1515/math-2015-0015",
issn = "2391-5455",
bib2html_dl_html = "http://dx.doi.org/10.1515/math-2015-0015",
abstract = "We study the problem of computing the maximal and minimal possible eigenvalues of a symmetric matrix when the matrix entries vary within compact intervals. In particular, we focus on computational complexity of determining these extremal eigenvalues with some approximation error. Besides the classical absolute and relative approximation errors, which turn out not to be suitable for this problem, we adapt a less known one related to the relative error, and also propose a novel approximation error. We show in which error factors the problem is polynomially solvable and in which factors it becomes NP-hard.",
keywords = "Interval matrix; Interval analysis; Eigenvalue; Eigenvalue bounds; NP-hardness",
}
Generated by bib2html.pl (written by Patrick Riley ) on Mon Apr 15, 2024 08:26:42