Freeze-Tag: Optimal Strategies for Awakening a Swarm of Robots

Given $n$ robots in a metric space, one initially awake robot moves at unit speed and awakens a sleeping robot upon reaching it; awakened robots may then move. Determine whether minimizing the time until all robots are awake is NP-hard in the Euclidean plane or the rectilinear plane. Also determine whether general metrics admit an $o(\log n)$ -approximation.

Download

Abstract

Determine the computational complexity and approximability of awakening sleeping robots in metric and planar geometric spaces as quickly as possible.

Background and progress

Arkin and coauthors introduced the problem, proved hardness for star metrics, obtained a PTAS in fixed-dimensional $L_p$ spaces, and gave an $O(\log n)$ approximation in general metrics [Arkin et al., 2002]. NP-hardness in the Euclidean or rectilinear plane and a better general-metric approximation remain open. The original problem appears in the Open Problems Project at https://topp.openproblem.net/p35.

Reference papers

The freeze-tag problem: How to wake up a swarm of robotsEsther M. Arkin, Michael A. Bender, Sándor P. Fekete, Joseph S. B. Mitchell, Martin SkutellaProceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms · 2002