Minimal reachability is hard to approximate

Thumbnail
Date Issued
2017
Publisher Version
10.1109/TAC.2018.2836021
Author(s)
Jadbabaie, Ali
Olshevsky, Alexander
Pappas, George J.
Tzoumas, Vasileios
Share to FacebookShare to TwitterShare by Email
Export Citation
Metadata
Show full item record
Permanent Link
https://hdl.handle.net/2144/34291
Version
Published version
Citation (published version)
Ali Jadbabaie, Alexander Olshevsky, George J Pappas, Vasileios Tzoumas. 2017. "Minimal Reachability is Hard To Approximate." IEEE Transactions on Automatic Control, https://doi.org/10.1109/TAC.2018.2836021
Abstract
In this note, we consider the problem of choosing, which nodes of a linear dynamical system should be actuated so that the state transfer from the system's initial condition to a given final state is possible. Assuming a standard complexity hypothesis, we show that this problem cannot be efficiently solved or approximated in polynomial, or even quasi-polynomial, time.
Rights
© 2011 IEEE.
Collections