Approximating the minimal sensor selection for supervisory control

Samir Khuller, Guy Kortsarz, Kurt R. Rohloff

Research output: Contribution to journalConference articlepeer-review

2 Scopus citations


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 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 cut 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.

Original languageEnglish (US)
Pages (from-to)87-92
Number of pages6
JournalIFAC Proceedings Volumes (IFAC-PapersOnline)
Issue number18
StatePublished - 2004
Externally publishedYes
Event7th International Workshop on Discrete Event Systems, WODES 2004 - Reims, France
Duration: Sep 22 2004Sep 24 2004

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering


  • Approximation algorithms
  • Computer-aided control system design
  • Discrete-event systems. supervisory control graph theory
  • Observers


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

Cite this