NDSU North Dakota State University
Fargo, N.D.
library-image

NDSU Institutional Repository

Deterministic Greedy Algorithms for Optimal Sensor Placement

Show full item record

Click to view higher resolution file
Venkata Chintamaneni.pdf
Title: Deterministic Greedy Algorithms for Optimal Sensor Placement
Author: Chintamaneni, Venkata Santosh
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.
Date: 2012
Subject: Computer Science.
Master of Science / Computer Science, College of Science and Mathematics, 2012.
Permalink: http://hdl.handle.net/10365/19526

This item appears in the following Collection(s)

Show full item record

Search DSpace



Advanced Search

Browse

Your Account