@inbook {13365,
	title = {Energy Efficient Monitoring in Sensor Networks},
	booktitle = {LATIN 2008: Theoretical InformaticsLATIN 2008: Theoretical Informatics},
	series = {Lecture Notes in Computer Science},
	volume = {4957},
	year = {2008},
	month = {2008///},
	pages = {436 - 448},
	publisher = {Springer Berlin / Heidelberg},
	organization = {Springer Berlin / Heidelberg},
	abstract = {In this paper we study a set of problems related to efficient energy management for monitoring applications in wireless sensor networks. We study several generalizations of a basic problem called Set k -Cover, which can be described as follows: we are given a set of sensors, and a set of regions to be monitored. Each region can be monitored by a subset of the sensors. To increase the lifetime of the sensor network, we would like to partition the sensors into k sets (or time-slots) and activate each partition in a different time-slot. The goal is to find the partitioning that maximizes the coverage of the regions. This problem is known to be NP -hard. We first develop improved approximation algorithms for this problem based on its similarities to the max k -cut problem. We then consider a variation, called Set ( k , α )-cover, where each sensor is allowed to be active in α different time-slots. We develop a randomized routing algorithm for this problem. We then consider extensions where each sensor can monitor only a bounded number of regions in any time-slot. We develop the first approximation algorithms for this problem. An experimental evaluation of the algorithms we propose can be found in the full version of the paper.},
	isbn = {978-3-540-78772-3},
	url = {http://dx.doi.org/10.1007/978-3-540-78773-0_38},
	author = {Deshpande, Amol and Khuller, Samir and Malekian,Azarakhsh and Toossi,Mohammed},
	editor = {Laber,Eduardo and Bornstein,Claudson and Nogueira,Loana and Faria,Luerbio}
}
