Approximating the minimal sensor selection for supervisory control

Kurt R. Rohloff, Samir Khuller, Guy Kortsarz

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)143-170
Number of pages28
JournalDiscrete Event Dynamic Systems: Theory and Applications
Issue number1
StatePublished - Jan 2006
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Modeling and Simulation
  • Electrical and Electronic Engineering


  • Approximation algorithms
  • Automata
  • Computational complexity
  • Sensor selection
  • Supervisory control


Dive into the research topics of 'Approximating the minimal sensor selection for supervisory control'. Together they form a unique fingerprint.

Cite this