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
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 L1) plane? In more general metric spaces, can
one obtain an approximation algorithm with better than O(log n)