Approximating constrained minimum cost input-output selection for generic arbitrary pole placement in structured systems

This paper deals with minimum cost constrained selection of inputs, outputs and feedback pattern in structured systems, referred to as optimal input-output and feedback co-design problem. 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 are pre-specified. Further, each input and each output are associated with a cost. The feedback pattern is unconstrained and the cost of a feedback edge is the sum of cost of the input and output associated with it. Our goal is to optimally select an input-output set and a feedback pattern such that the closed-loop system has no structurally fixed modes (SFMs). This problem is known to be NP-hard. In this paper, we show that the problem is inapproximable to factor (1 - o(1)) log n, where n denotes the number of states in the system. Then we present an approximation algorithm of time complexity O(n(3)) to approximate the problem. We prove that the proposed algorithm gives a (2 log n)-approximate solution to the problem. Thus the algorithm given in this paper is an order optimal approximation algorithm to approximate the optimal input-output and feedback co-design problem. (C) 2019 Elsevier Ltd. All rights reserved.