  This paper addresses optimal feedback selection for generic arbitrary pole
placement of structured systems when each feedback edge is associated with a
cost. Given a structured system and a feedback cost matrix, our aim is to find
a feasible feedback matrix of minimum cost that guarantees arbitrary pole
placement of the closed-loop structured system. We first give a polynomial time
reduction of the weighted set cover problem to an instance of the feedback
selection problem and thereby show that the problem is NP-hard. Then we prove
the inapproximability of the problem by showing that constant factor
approximation for the problem does not exist unless the set cover problem can
be approximated within a constant factor. Since the problem is hard, we study a
subclass of systems whose directed acyclic graph constructed using the strongly
connected components of the state digraph is a line graph and the state
bipartite graph has a perfect matching. We propose a polynomial time optimal
algorithm based on dynamic programming for solving the problem on this class of
systems. Further, over the same class of systems we relax the perfect matching
assumption, and provide a polynomial time 2-optimal solution based on dynamic
programming and a minimum cost perfect matching algorithm.
