Probabilistic solutions to some NP-hard matrix problems
(2001) Automatica — Vol. 37, n° 9, p. 1397-1405 (2001)
Files
pdfdocument.pdf
Restricted Access - Adobe PDF
- 163.32 KB
Details
- Authors
- Abstract
- During recent years, it has been shown that a number of problems in matrix theory are NP-hard, including robust nonsingularity, robust stability, robust positive semidefiniteness. robust bounded norm, state feedback stabilization with structural and norm constraints, etc. In this paper, we use standard bounds on empirical probabilities as well as recent results from statistical learning theory on the VC-dimension of families of sets defined by a finite number of polynomial inequalities, to show that for each of the above problems, as well as for still more general and more difficult problems, there exists a polynomial-time randomized algorithm that can provide a yes or no answer to arbitrarily small levels of accuracy and confidence. (C) 2001 Elsevier Science Ltd. All rights reserved.
- Affiliations
Citations
Vidyasagar, M., & Blondel, V. (2001). Probabilistic solutions to some NP-hard matrix problems. Automatica, 37(9), 1397-1405. https://doi.org/10.1016/S0005-1098(01)00089-9 (Original work published 2001)