  We address the problem of minimal actuator placement in linear systems so
that the volume of the set of states reachable with one unit or less of input
energy is lower bounded by a desired value. First, following the recent work of
Olshevsky, we prove that this is NP-hard. Then, we provide an efficient
algorithm which, for a given range of problem parameters, approximates up to a
multiplicative factor of O(logn), n being the network size, any optimal
actuator set that meets the same energy criteria; this is the best
approximation factor one can achieve in polynomial time, in the worst case.
Moreover, the algorithm uses a perturbed version of the involved control energy
metric, which we prove to be supermodular. Next, we focus on the related
problem of cardinality-constrained actuator placement for minimum control
effort, where the optimal actuator set is selected to maximize the volume of
the set of states reachable with one unit or less of input energy. While this
is also an NP-hard problem, we use our proposed algorithm to efficiently
approximate its solutions as well.
