2006.08.08 | Gerth Stølting Brodal

Adam Buchsbaum, AT&T Research

Title: Restricted Strip Covering and the Sensor Cover Problem

Supposewe are given a set of objects that cover a region and a duration
associated with each object. Viewing the objects as jobs, can we schedule
their beginning times to maximizethe length of time that the original
region remains covered? This is the Sensor Cover Problem. For example,
suppose you wish to monitor activity along a fence (interval) by sensors
placed at various fixed locations. Each sensor has a range (also an
interval) and limited battery life. The problem is then 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 onthe 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 bottom position to each rectangle
(by moving them up or down) so as 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 (rectangles may not overlap, and the goal is to
minimize the highest point covered), then the problem becomes identical
to Dynamic Storage Allocation, a well-studied schedulingproblem, which
is in turn a restricted case of the well known problem Strip Packing.

We present a collection of algorithms for Restricted Strip Covering.
We show that theproblem is NP-hard and present an O(logloglog n)-
approximation algorithm. We also present better approximation or
exact algorithms for some special cases, including when all intervals
have equal width. For the general Sensor Cover Problem, we distinguish
between cases in which elements have uniform or variable durations.
The results depend on the structure of the region to be covered: We
give a polynomial-time, exact algorithm for the uniform-duration case
of Restricted Strip Covering but prove that the uniform-duration case
for higher-dimensional regions is NP-hard.We give some more specific
results for two-dimensional regions.

This is joint work with Alon Efrat, Shaili Jain, Suresh
Venkatasubramanian, and Ke Yi.