Linear time constant factor approximation algorithm for the Euclidean ``Freeze-Tag`` robot awakening problem

Abstract

The Freeze-Tag Problem (FTP) arises in the study of swarm robotics. The FTP is a combinatorial optimization problem that starts by locating a set of robots in a Euclidean plane. Here, we are given a swarm of n asleep (frozen or inactive) robots and a single awake (active) robot. In order to activate an inactive robot in FTP, the active robot should either be in the physical proximity to the inactive robot or ``touch`` it. The new activated robot starts moving and can wake up other inactive robots. The goal is to find an optimal activating schedule with the minimum time required for activating all robots. In general, FTP is an NP-Hard problem and in the Euclidean space is an open problem. In this paper, we present a recursive approximation algorithm with a constant approximation factor and a linear running time for the Euclidean Freeze-Tag Problem.