TY - GEN
T1 - The freeze-tag problem
T2 - 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
AU - Arkin, Esther M.
AU - Bender, Michael A.
AU - Fekete, Sándor P.
AU - Mitchell, Joseph S.B.
AU - Skutella, Martin
PY - 2002
Y1 - 2002
N2 - 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 assists 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∗. We consider both scenarios on graphs and in geometric environments. In the graph setting, robots sleep at vertices and there is 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 A)-competitive for graphs with maximum degree A. 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 ultrametrics, there is a polynomial-time approximation algorithm with performance ratio 2O(√ log log n)). (4) There is a PTAS, running in nearly linear time, for geometrically embedded instances (e.g., Euclidean distances in any fixed dimension).
AB - 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 assists 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∗. We consider both scenarios on graphs and in geometric environments. In the graph setting, robots sleep at vertices and there is 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 A)-competitive for graphs with maximum degree A. 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 ultrametrics, there is a polynomial-time approximation algorithm with performance ratio 2O(√ log log n)). (4) There is a PTAS, running in nearly linear time, for geometrically embedded instances (e.g., Euclidean distances in any fixed dimension).
UR - https://www.scopus.com/pages/publications/84968918943
M3 - Conference contribution
AN - SCOPUS:84968918943
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 568
EP - 577
BT - Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
PB - Association for Computing Machinery
Y2 - 6 January 2002 through 8 January 2002
ER -