direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 711-2001

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

The Freeze-Tag Problem: How to Wake Up a Swarm of Robots
Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Joseph S. B. Mitchell, and Martin Skutella
Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'02), Society of Industrial and Applied Mathematics (2002), 568-577
primary: 68W25 Approximation algorithms
secondary: 90B35 Scheduling theory, deterministic
68T40 Robotics
scheduling, makespan, broadcasting, information distribution, robot control, approximation, NP-completeness, lower bounds for approximation
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).
The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe