Minimal Reachability is Hard To Approximate

DOI10.1109/TAC.2018.2836021MaRDI QIDQ4629833zbMATH OpenOpenAlexFDO

Authors Ali Jadbabaie, Alex Olshevsky, George Pappas, Vasileios Tzoumas

Publication date 28 March 2019

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.10244

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Large-scale systems (93A15) Controllability (93B05) Linear systems in control theory (93C05)

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.

Cited in

(5)

• Resource-aware time-optimal control with multiple sparsity measures
• Leader selection in networks under switching topologies with antagonistic interactions
• A separation theorem for joint sensor and actuator scheduling with guaranteed performance bounds
• Sparse control for continuous‐time systems
• A survey on compressed sensing approach to systems and control

This page was built for publication: Minimal Reachability is Hard To Approximate

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4629833)