  This paper is about minimum cost constrained selection of inputs and outputs
for generic arbitrary pole placement. The input-output set is constrained in
the sense that the set of states that each input can influence and the set of
states that each output can sense is pre-specified. Our goal is to optimally
select an input-output set that the system has no structurally fixed modes.
Polynomial algorithms do not exist for solving this problem unless P=NP. To
this end, we propose an approximation algorithm by splitting the problem in to
three sub-problems: a) minimum cost accessibility problem, b) minimum cost
sensability problem and c) minimum cost disjoint cycle problem. We prove that
problems a) and b) are equivalent to a suitably defined weighted set cover
problems. We also show that problem c) is equivalent to a minimum cost perfect
matching problem. Using these we give an approximation algorithm which solves
the minimum cost generic arbitrary pole placement problem. The proposed
algorithm incorporates an approximation algorithm to solve the weighted set
cover problem for solving a) and b) and a minimum cost perfect matching
algorithm to solve c). Further, we show that the algorithm is polynomial time
an gives an order optimal solution to the minimum cost input-output selection
for generic arbitrary pole placement problem.
