Wake a swarm of frozen robots with a chain-reaction schedule — then send them all back home, and watch the makespan jump.
Grounded in
"Freeze-Tag with Return" (arXiv:
2606.21985),
Bonichon, Gavoille, Hanusse, Le Bouder, Marcé & Morawietz. The classic
Freeze-Tag Problem starts with one awake robot and
n sleeping ones scattered in a region; the awake robot must travel to touch (wake) sleeping robots, and every robot it wakes can
immediately help wake others too — a branching chain reaction — with the goal of minimizing the
makespan: the time until everyone is
awake. This paper studies the
"with return" variant, where every robot must also make it back to the starting point once the swarm is
fully awake. For robots scattered anywhere in a unit disk, they prove the ratio of the with-return optimal makespan to the plain (open)
optimal makespan always sits between
1.732 and
1.959 — and if the robots happen to sit in
convex position, they tighten a
related bound to at most
2+2√2 ≈ 4.828.
Honesty check: this toy runs a simple greedy heuristic (nearest-available-mover-to-nearest-target), not the paper's optimal
algorithm — it's a genuine, correctly-simulated scheduler, just not a provably-optimal one. Because the greedy scheduler optimizes only
for waking robots quickly and never thinks ahead about the walk home, the with-return ratio you see below can land outside the
theorem's proven range for true optimal schedules — that gap is exactly what the paper's real algorithm closes. It's also worth noting the
paper's headline theorem is stated as a bound on the difference between the two makespans; this demo reframes it as a ratio
(as requested) so a small random instance and a huge one can be compared on the same scale.