An optimization problem that naturally arises in the study of
"swarm robotics" is to wake up a set of "asleep" robots, starting
with only one "awake" robot. A robot is awakened when
another awake robot gets to it. As soon as a robot is awake, it can
assist in waking up other robots. The goal is to compute an optimal
awakening schedule that results in all robots being awake by
time t^*, for the smallest possible value of t^*.
We consider
both scenarios on graphs and in geometric environments.
In the graph setting,
robots sleep at vertices, with a length function on the
edges. An awake robot can travel from vertex to vertex
along edges,
and the length of an edge determines the time it takes to travel from
one vertex to the other.
While this problem bears some resemblance to problems from various
areas in combinatorial optimization such as routing, broadcasting,
scheduling and covering, its algorithmic characteristics are
surprisingly different. We prove that the problem is NP-hard, even
for the special case of star graphs. We also establish hardness of
approximation, showing that it is NP-hard to obtain an approximation
factor better than 5/3, even for graphs of bounded degree.
These lower bounds are complemented with several algorithmic
results. We present a simple on-line algorithm
that is O(logΔ)-competitive
for graphs with maximum degree Δ. Other results
include algorithms that require substantially more sophistication
and development of new techniques: (1) The natural greedy strategy
on star graphs has a worst-case performance of 7/3, which is tight.
(2) There exists a PTAS for star graphs. (3) For the problem on
tree graphs, there is a polynomial-time approximation algorithm with
performance ratio 2O( loglog n)}. (4) There is
a PTAS, running in nearly linear time, for geometrically
embedded instances
(e.g., Euclidean distances in any fixed dimension).
