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.
One robot can only awaken another when they are in the same location.
As soon as a robot is awake, it may
assist in waking up other robots. The goal is to compute an optimal
awakening schedule such that all robots are awake by
time t^{*}, for the smallest possible value of t^{*} (the optimal
makespan).
The n robots are initially at n points of a metric space.
The problem is equivalent to finding a spanning tree with maximum out-degree
two that minimizes the radius from a fixed source.
Is it NP-hard to determine an optimal awakening schedule for robots in
the Euclidean (or L_{1}) plane? In more general metric spaces, can
one obtain an approximation algorithm with better than O(log n)
performance ratio?