clopen.solutions
OP-01084 Open

Complexity and approximation of the freeze-tag problem

Submit a result

In the freeze-tag problem, $n$ robots sit at $n$ points of a metric space. One robot is awake and the others are asleep; robots travel at unit speed, a robot wakes a sleeping one by reaching its location, and every awakened robot may then help wake others. An awakening schedule is sought that minimizes the makespan, the time by which all robots are awake. Equivalently, one seeks a spanning tree rooted at the initially awake robot, every node having at most two children, whose radius measured from the root is as small as possible.

Arkin, Bender, Fekete, Mitchell and Skutella proved the problem NP-complete in star metrics, gave a PTAS for $L_p$ metrics in fixed dimension and an $O(\log n)$-approximation in general metric spaces, and conjectured NP-hardness in the Euclidean and $L_1$ planes.

Problem. When the robots lie in the Euclidean plane, or in the plane with the $L_1$ metric, is finding a schedule of minimum makespan NP-hard? For general metric spaces, does some polynomial-time approximation algorithm achieve a performance ratio better than $O(\log n)$?

Source: Arkin, Bender, Fekete, Mitchell and Skutella (2002); Problem 35 of The Open Problems Project (Demaine, Mitchell and O'Rourke).

Imported from topp.openproblem.net.

Classification

Primary
OC — Optimization and Control
Secondary
CO, MG
Keywords
approximation algorithms, freeze-tag problem, NP-hardness, The Open Problems Project

References

@inproceedings{arkin2002,
  author    = {Arkin, E. M. and Bender, M. A. and Fekete, S. P. and Mitchell, J. S. B. and Skutella, M.},
  title     = {The Freeze-Tag Problem: How to Wake Up a Swarm of Robots},
  booktitle = {Proc. 13th ACM-SIAM Sympos. Discrete Algorithms},
  year      = {2002},
  pages     = {568--577},
}

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-01084, "Complexity and approximation of the freeze-tag problem", clopen.solutions.