  Actuator placement is an active field of research which has received
significant attention for its applications in complex dynamical networks. In
this paper, we study the problem of finding a set of actuator placements
minimizing the metric that measures the average energy consumed for state
transfer by the controller, while satisfying a structural controllability
requirement and a cardinality constraint on the number of actuators allowed. As
no computationally efficient methods are known to solve such combinatorial set
function optimization problems, two greedy algorithms, forward and reverse, are
proposed to obtain approximate solutions. We first show that the constraint
sets these algorithms explore can be characterized by matroids. We then obtain
performance guarantees for the forward and reverse greedy algorithms applied to
the general class of matroid optimization problems by exploiting properties of
the objective function such as the submodularity ratio and the curvature.
Finally, we propose feasibility check methods for both algorithms based on
maximum flow problems on certain auxiliary graphs originating from the network
graph. Our results are verified with case studies over large networks.
