TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)2001

COGA 5-Wheel

Page Content

to Navigation

Preprints 2001

The Freeze-Tag Problem: How to Wake Up a Swarm of Robots
Citation key Report-711-2001
Author Esther M. Arkin and Michael A. Bender and Sándor P. Fekete and Joseph S. B. Mitchell and Martin Skutella
Year 2001
Number 711
Note Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'02), Society of Industrial and Applied Mathematics (2002), 568-577
Institution Technische Universität Berlin, Institut für Mathematik
Abstract 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(łog\Delta)$-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 $2^O(\sqrtn)$. (4) There is a PTAS, running in nearly linear time, for geometrically embedded instances (e.g., Euclidean distances in any fixed dimension).
Bibtex Type of Publication Preprint
Download Bibtex entry

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe