Harvard Theory of Computation Seminar
Restricted Strip Covering and the Sensor Cover Problem
Shaili Jain, Harvard University
Place and Time: WEDNESDAY 2/15, Maxwell-Dworkin 319
Refreshments at 2:30, talk at 2:45.
ABSTRACT
Suppose we 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 maximize the length of
time that the original region remains covered? We call this problem
the sensor cover problem. It arises in the context of covering a
region with sensors. 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 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 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 is identical to dynamic storage allocation, a
well-studied scheduling problem that 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 the problem is NP-hard and present an O(log
log n)-approximation algorithm. We also present better
approximation or exact algorithms for some special cases. 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. Finally, we consider
regions that are arbitrary sets, and we present an O(log
n)-approximation algorithm for the most general case.
Joint work with Adam Buchsbaum, Alon Efrat, Suresh
Venkatasubramanian and Ke Yi.