Journal
IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS
Volume 1, Issue 3, Pages 249-258Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TCNS.2014.2337974
Keywords
Controllability; control design; linear feedbackc control systems
Funding
- NSF [ECCS-1351684]
- Div Of Electrical, Commun & Cyber Sys
- Directorate For Engineering [1351684] Funding Source: National Science Foundation
Ask authors/readers for more resources
Given a linear system, we consider the problem of finding a small set of variables to affect with an input so that the resulting system is controllable. We show that this problem is NP-hard; indeed, we show that even approximating the minimum number of variables that need to be affected within a multiplicative factor of c log n is NP-hard for some positive c. On the positive side, we show it is possible to find sets of variables matching this inapproximability barrier in polynomial time. This can be done with a simple greedy heuristic which sequentially picks variables to maximize the rank increase of the controllability matrix. Experiments on Erdos-Renyi random graphs that demonstrate this heuristic almost always succeed at findingng the minimum number of variables.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available