Paper Info
Title
Approximating Constrained Minimum Cost Input-Output Selection for Generic Arbitrary Pole Placement in Structured Systems.
Abstract
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))logn, where n denotes the number of states in the system. Then we present an approximation algorithm of time complexity O(n3) to approximate the problem. We prove that the proposed algorithm gives a (2logn)-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.
Year
DOI
Venue
2017
10.1016/j.automatica.2019.05.002
Automatica
Keywords
Field
DocType
Linear structured systems,Pole placement,Input–output selection,Approximation algorithms,Complex networks
Approximation algorithm,Discrete mathematics,Set cover problem,Mathematical optimization,Disjoint sets,Matching (graph theory),Input/output,Time complexity,Minimum k-cut,Mathematics,Minimum-cost flow problem
Journal
Volume
Issue
ISSN
107
1
0005-1098
Citations 
PageRank 
References 
1
0.36
0
Authors
3
Name
Order
Citations
PageRank
Shana Moothedath111.71
Prasanna Chaporkar221925.60
Madhu N. Belur33713.87