  In this paper, we investigate the problem of actuator selection for linear
dynamical systems. We develop a framework to design a sparse actuator schedule
for a given large-scale linear system with guaranteed performance bounds using
deterministic polynomial-time and randomized approximately linear-time
algorithms. First, we introduce systemic controllability metrics for linear
dynamical systems that are monotone and homogeneous with respect to the
controllability Gramian. We show that several popular and widely used
optimization criteria in the literature belong to this class of controllability
metrics. Our main result is to provide a polynomial-time actuator schedule that
on average selects only a constant number of actuators at each time step,
independent of the dimension, to furnish a guaranteed approximation of the
controllability metrics in comparison to when all actuators are in use. Our
results naturally apply to the dual problem of sensor selection, in which we
provide a guaranteed approximation to the observability Gramian. We illustrate
the effectiveness of our theoretical findings via several numerical simulations
using benchmark examples.
