Approximating the Minimal Sensor Selection for Supervisory Control

This paper discusses the problem of selecting a set of sensors of minimum cardinality that can be used for the synthesis of a supervisory controller.  We show how this sensor selection problem is realted to a type of directed st-cut problem that has not been previously discussed in the literature.  Approximation algorithms to solve the sensor selection problem can be used to solve the graph cutting problem and vice-versa.  Polynomial time algorithms to find good approximate solutions to either problem most likely do not exist (under certain complexity assumptions), but a time efficient approximation algorithm is shown that solves a special case fo these problems