Minimal Reachability is Hard to Approximate
© 1963-2012 IEEE. 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 proble...
| Main Authors: | , , , |
|---|---|
| Andre forfattere: | |
| Format: | Article |
| Sprog: | English |
| Udgivet: |
Institute of Electrical and Electronics Engineers (IEEE)
2023
|
| Online adgang: | https://hdl.handle.net/1721.1/148591 |
| _version_ | 1826211337991094272 |
|---|---|
| author | Jadbabaie, A Olshevsky, A Pappas, GJ Tzoumas, V |
| author2 | Massachusetts Institute of Technology. Department of Civil and Environmental Engineering |
| author_facet | Massachusetts Institute of Technology. Department of Civil and Environmental Engineering Jadbabaie, A Olshevsky, A Pappas, GJ Tzoumas, V |
| author_sort | Jadbabaie, A |
| collection | MIT |
| description | © 1963-2012 IEEE. 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. |
| first_indexed | 2024-09-23T15:04:20Z |
| format | Article |
| id | mit-1721.1/148591 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:04:20Z |
| publishDate | 2023 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1485912023-03-18T03:10:12Z Minimal Reachability is Hard to Approximate Jadbabaie, A Olshevsky, A Pappas, GJ Tzoumas, V Massachusetts Institute of Technology. Department of Civil and Environmental Engineering Massachusetts Institute of Technology. Institute for Data, Systems, and Society © 1963-2012 IEEE. 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. 2023-03-17T13:53:10Z 2023-03-17T13:53:10Z 2019-02-01 2023-03-17T12:17:29Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/148591 Jadbabaie, A, Olshevsky, A, Pappas, GJ and Tzoumas, V. 2019. "Minimal Reachability is Hard to Approximate." IEEE Transactions on Automatic Control, 64 (2). en 10.1109/TAC.2018.2836021 IEEE Transactions on Automatic Control Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) other univ website |
| spellingShingle | Jadbabaie, A Olshevsky, A Pappas, GJ Tzoumas, V Minimal Reachability is Hard to Approximate |
| title | Minimal Reachability is Hard to Approximate |
| title_full | Minimal Reachability is Hard to Approximate |
| title_fullStr | Minimal Reachability is Hard to Approximate |
| title_full_unstemmed | Minimal Reachability is Hard to Approximate |
| title_short | Minimal Reachability is Hard to Approximate |
| title_sort | minimal reachability is hard to approximate |
| url | https://hdl.handle.net/1721.1/148591 |
| work_keys_str_mv | AT jadbabaiea minimalreachabilityishardtoapproximate AT olshevskya minimalreachabilityishardtoapproximate AT pappasgj minimalreachabilityishardtoapproximate AT tzoumasv minimalreachabilityishardtoapproximate |