A PTAS for geometric 2-FTP

• In FTP, some inactive robots should be activated by only one initial active robot.
• Each active robot can assist in activating other inactive robots, by closing to them.
• The goal is activating all inactive robots within the minimum time.
• We introduce k  -FTP, a generalization of FTP, where we have k>1k>1 initial active robots.
• We give a constant factor approximation algorithm for k-FTP and a PTAS for 2-FTP.

The Freeze Tag Problem (FTP) is an optimization problem that arises in Swarm Robotics. This problem studies the way of activating a group of inactive robots using only one active robot. In FTP for activating an inactive robot, the active robot should be in the physical proximity of it. The new activated robot can assist in activating other inactive robots. The goal is to find an optimal activating schedule with the minimum time required for activating all robots. In this paper, we investigate k-FTP which is a generalization of FTP where we have k   initial active robots at first instead of only one active robot. We give an approximation algorithm and a PTAS for 2-FTP (k=2k=2).