NDSU North Dakota State University
Fargo, N.D.

NDSU Institutional Repository

Deterministic Greedy Algorithms for Optimal Sensor Placement

Show simple item record

dc.description.abstract A sensor is a device which can be sensitive to any physical stimulus, such as light, heat, or a particular motion, and responds with a respective impulse. A graph is an abstract representation for a set of objects of any kind where some object pairs are connected by links. The interconnected objects are called vertices or nodes. In this paper, one of the antiquated and classical examples of a Non-Deterministic Polynomial hard (NP-hard) optimization problem in computer science, the “Set Coverage Problem,” is discussed. Monitoring spatial constraints in real-world networks with huge data requires the best sensor placement for a given network. For any typical network, it has been proven that a greedy placement algorithm achieves a minimum of 63% optimal reduction in total variance. The focus in this paper is on sensor-optimization problem with the help of two approximation algorithms inherited from traditional greedy approach with supporting experimental results. en_US
dc.title Deterministic Greedy Algorithms for Optimal Sensor Placement en_US
dc.date.accessioned 2012-04-02T13:19:29Z
dc.date.available 2012-04-02T13:19:29Z
dc.date.issued 2012-04-02
dc.identifier.uri http://hdl.handle.net/10365/19526
dc.thesis.degree Paper(M.S.)--North Dakota State University, 2012.
dc.contributor.advisor Nygard, Kendall en_US
dc.subject.lcsh Computer algorithms.
dc.subject.lcsh Approximation algorithms.
dc.subject.lcsh Detectors.
dc.subject.lcsh Electric power system stability.
dc.subject.lcsh Electric power systems -- Reliability.
dc.creator.author Chintamaneni, Venkata Santosh
dc.degree.departmentCollege Master of Science / Computer Science, College of Science and Mathematics, 2012.
dc.date.created 2012

This item appears in the following Collection(s)

Show simple item record

Search DSpace

Advanced Search


Your Account