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

Mohammad Javad Namazifar, Alireza Bagheri, Keivan Borna


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.


Freeze Tag Problem; Recursive Algorithm; Optimization; Swarm Robotics; Computational Geometry

Full Text:


Lululemon Black Friday cheap nfl jerseys Lululemon factory Outlet ny Black Friday discount tiffany outlet wholesale soccer jerseys online oakley black friday cheap nhl jerseys china cheap nfl jerseys north face black friday sale cheap nfl jerseys online Jordans Black Friday Sale 2015 Cheap Moncler Cyber Monday moncler outlet cheap soccer jerseys moncler outlet black friday cheap authentic nfl jerseys north face cyber monday Louboutin Black Friday canada wholesale cheap nfl jerseys lululemon cyber monday 2015 cheap nfl jerseys from china 2015 Cheap Moncler Black Friday Sale Moncler Cyber Monday 2015 cheap jerseys Lululemon Cyber Monday Sale jordans cyber monday deals 2015 cheap nike nfl jerseys Black Friday deals Lululemon 2015 jordan black friday 2015 Moncler Jackets Black Friday Sale 2015 Louboutin Pas Cher Black Friday 2015 Canada Lululemon north face black friday cheap wholesale soccer jerseys