Abstract:

In this talk a simplification problem for systems of linear inequalities describing precedence relation systems is considered. Given a precedence relation system, the problem seeks a minimum equivalent subset of the precedence relations (i.e., inequalities) which has the same solution set as that of the original system. The problem is shown to be NP-hard. However, a sufficient condition is derived under which the problem is solvable in polynomial-time. In addition, a decomposition of the first problem into independent tractable and intractable subproblems is derived. A general (not necessarily polynomial-time) solution construction procedure based on the decomposition is presented. The optimality of the procedure is proved. The result generalizes the one in [Moyles and Thompson 1969] for the minimum equivalent graph problem for unweighted directed graphs.

Speaker's Biography:

Kin Cheong Sou received a Ph.D. degree in Electrical Engineering and Computer Science at Massachusetts Institute of Technology in 2008. From 2008 to 2010 he was a postdoctoral researcher at Lund University, Lund, Sweden. From 2010 to 2012 he was a postdoctoral researcher at KTH Royal Institute of Technology, Stockholm, Sweden. Until December 2016 he was an associate professor (docent) with the department of Mathematical Sciences, Chalmers University of Technology and the University of Gothenburg, Sweden. Dr. Sou has been with National Sun Yat-sen University in Taiwan since February 2017. 

His research interests include cyber-physical systems analysis and design, smart grid and cities, discrete and graph optimization and theory, convex/non-convex optimization and dynamic systems theory.