Title :
Degree of Redundancy of Linear Systems Using Implicit Set Covering
Author :
Arellano, John D. ; Hicks, Illya V.
Author_Institution :
Dept. of Comput. & Appl. Math., Rice Univ., Houston, TX, USA
Abstract :
In this paper, we present a set covering problem (SCP) formulation to compute the degree of redundancy of linear systems. Computing the degree of redundancy of a linear system allows for the evaluation of the quality of the sensor network. The formulation is equivalent to solving the linear matroid cogirth problem, finding the cardinality of the smallest cocircuit of a matroid. We also discuss existing methods developed to solve the matroid cogirth problem and the SCP. Computational results are provided to validate a branch-and-cut algorithm that addresses the SCP formulation.
Keywords :
combinatorial mathematics; linear systems; matrix algebra; sensors; tree searching; SCP formulation; branch-and-cut algorithm; degree of redundancy; implicit set covering problem; linear matroid cogirth problem; linear systems; matroid cocircuit; sensor network quality; Greedy algorithms; Linear matrix inequalities; Linear programming; Linear systems; Redundancy; Vectors; Matroids; NP-hard; cogirth; degree of redundancy; girth; linear matroid; sensor networks; set covering problem;
Journal_Title :
Automation Science and Engineering, IEEE Transactions on
DOI :
10.1109/TASE.2013.2271703
