TY - GEN
T1 - Analysis of heuristics for the freeze-tag problem
AU - Sztainberg, Marcelo O.
AU - Arkin, Esther M.
AU - Bender, Michael A.
AU - Mitchell, Joseph S.B.
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.
PY - 2002
Y1 - 2002
N2 - In the Freeze Tag Problem (FTP) we are given a swarm of n asleep (frozen or inactive) robots and a single awake (active) robot, and we want to awaken all robots in the shortest possible time. A robot is awakened when an active robot “touches” it. 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 devise and test heuristic strategies on geometric and network datasets. Our experiments show that all of the strategies perform well, with the simple greedy strategy performing particularly well. A theoretical analysis of the greedy strategy gives a tight approximation bound of Θ(√log n) for points in the plane. We show more generally that the (tight) performance bound is Θ((log n)1−1/d) in d dimensions. This is in contrast to general metric spaces, where greedy is known to have a Θ(log n) approximation factor, and no method is known to achieve an approximation bound of o(log n).
AB - In the Freeze Tag Problem (FTP) we are given a swarm of n asleep (frozen or inactive) robots and a single awake (active) robot, and we want to awaken all robots in the shortest possible time. A robot is awakened when an active robot “touches” it. 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 devise and test heuristic strategies on geometric and network datasets. Our experiments show that all of the strategies perform well, with the simple greedy strategy performing particularly well. A theoretical analysis of the greedy strategy gives a tight approximation bound of Θ(√log n) for points in the plane. We show more generally that the (tight) performance bound is Θ((log n)1−1/d) in d dimensions. This is in contrast to general metric spaces, where greedy is known to have a Θ(log n) approximation factor, and no method is known to achieve an approximation bound of o(log n).
UR - https://www.scopus.com/pages/publications/84943245562
U2 - 10.1007/3-540-45471-3_28
DO - 10.1007/3-540-45471-3_28
M3 - Conference contribution
AN - SCOPUS:84943245562
SN - 9783540438663
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 270
EP - 279
BT - Algorithm Theory - SWAT 2002 - 8th Scandinavian Workshop on Algorithm Theory, Proceedings
A2 - Penttonen, Martti
A2 - Schmidt, Erik Meineche
PB - Springer Verlag
T2 - 8th Scandinavian Workshop on Algorithm Theory, SWAT 2002
Y2 - 3 July 2002 through 5 July 2002
ER -