Restricted Strip Covering and the Sensor Cover Problem

Details Restricted Strip Covering and the Sensor Cover Problem Restricted Strip Covering and the Sensor Cover Problem

2006-05-24

arxiv.org/abs/cs/0605102v1

Computer Science

Data Structures and Algorithms

14 pages, 6 figures

Scientific paper

Given a set of objects with durations (jobs) that cover a base region, can we schedule the jobs to maximize the duration the original region remains covered? We call this problem the sensor cover problem. This problem arises in the context of covering a region with sensors. For example, suppose you wish to monitor activity along a fence by sensors placed at various fixed locations. Each sensor has a range and limited battery life. The problem is to schedule when to turn on the sensors so that the fence is fully monitored for as long as possible. This one dimensional problem involves intervals on the real line. Associating a duration to each yields a set of rectangles in space and time, each specified by a pair of fixed horizontal endpoints and a height. The objective is to assign a position to each rectangle to maximize the height at which the spanning interval is fully covered. We call this one dimensional problem restricted strip covering. If we replace the covering constraint by a packing constraint, the problem is identical to dynamic storage allocation, a scheduling problem that is a restricted case of the strip packing problem. We show that the restricted strip covering problem is NP-hard and present an O(log log n)-approximation algorithm. We present better approximations or exact algorithms for some special cases. For the uniform-duration case of restricted strip covering we give a polynomial-time, exact algorithm but prove that the uniform-duration case for higher-dimensional regions is NP-hard. Finally, we consider regions that are arbitrary sets, and we present an O(log n)-approximation algorithm.

Affiliated with

Also associated with

No associations

Rating

Restricted Strip Covering and the Sensor Cover Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Restricted Strip Covering and the Sensor Cover Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Restricted Strip Covering and the Sensor Cover Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-71406