Algorithms for Scheduling Sensors to Maximize Coverage Time

Rafael da Ponte Barbosa () and Yoshiko Wakabayashi ()
Additional contact information
Rafael da Ponte Barbosa: Universidade de São Paulo, Instituto de Matemática e Estatística
Yoshiko Wakabayashi: Universidade de São Paulo, Instituto de Matemática e Estatística

A chapter in Facets of Combinatorial Optimization, 2013, pp 195-214 from Springer

Abstract: Abstract We study a one-dimensional sensor cover problem, known as the Restricted Strip Cover (RSC) problem, defined as follows. We are given an interval U of the real line, and a set of n sensors, each of which covers some subinterval of U and is powered with a battery of limited duration. The RSC problem consists in finding a scheduling of the sensors (that is, an assignment of the activating times of the given sensors) so that the whole interval U is covered for as long as possible. We investigate two variants of this problem: one denoted simply as RSC, the non-preemptive variant; and the other, denoted as RSCP, the preemptive variant. In the first, each sensor can be activated at most once and it remains on through the duration of its battery. In the second variant, preemption is allowed, that is, each sensor can be activated and deactivated many times along the duration of its battery. Buchsbaum, Efrat, Jain, Venkatasubramanian and Yi showed that RSC is NP-hard and designed an O(loglogn)-approximation algorithm. More recently, Gibson and Varadarajan presented a greedy-like algorithm which they proved to have approximation ratio at most 5. We prove that the approximation ratio of this algorithm is 4, and exhibit an instance showing that this ratio analysis is tight. We also show an integer programming formulation for this problem and present some computational results obtained with the implementation of this approach. For the same set of instances, we compute the quality of the solution found by the approximation algorithm. For the preemptive variant RSCP, we present an exact polynomial-time algorithm.

Keywords: Approximation Algorithm; Approximation Ratio; Polynomial Time Approximation Scheme; Additional Part; Integer Programming Formulation (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-38189-8_9

Ordering information: This item can be ordered from
http://www.springer.com/9783642381898

DOI: 10.1007/978-3-642-38189-8_9

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().