Minimal reachability is hard to approximate
Permanent Link
https://hdl.handle.net/2144/34291Version
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.2836021Abstract
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
Related items
Showing items related by title, author, creator and subject.
-
Reconstruction of fine-scale auroral dynamics
(IEEE-Inst Electrical Electronics Engineers Inc, 2016-05-01)We present a feasibility study for a high frame rate, short baseline auroral tomographic imaging system useful for estimating parametric variations in the precipitating electron number flux spectrum of dynamic auroral ... -
Riemannian consensus for manifolds with bounded curvature
(IEEE, 2013-04-01)Consensus algorithms are popular distributed algorithms for computing aggregate quantities, such as averages, in ad-hoc wireless networks. However, existing algorithms mostly address the case where the measurements lie in ... -
Control communication complexity of distributed actions
(IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC, 2012-11-01)Recent papers have treated control communication complexity in the context of information-based, multiple agent control systems including nonlinear systems of the type that have been studied in connection with ...
