@article {15248, title = {Approximating the minimal sensor selection for supervisory control}, journal = {Discrete Event Dynamic Systems}, volume = {16}, year = {2006}, month = {2006///}, pages = {143 - 170}, abstract = {This paper discusses the problem of selecting a set of sensors of minimum cost that can be used for the synthesis of a supervisory controller. It is shown how this sensor selection problem is related to a type of directed graph 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 of these problems. It is also shown how to convert the sensor selection problem into an integer programming problem.}, doi = {10.1007/s10626-006-6187-3}, author = {Rohloff,K. R and Khuller, Samir and Kortsarz,G.} }