A PTAS for geometric 2-FTP

作者：Moezkarimi Zahra^*; Bagheri Alireza

来源：Information Processing Letters, 2014, 114(12): 670-675.

DOI：10.1016/j.ipl.2014.06.017

• Freeze tag problem
• Swarm robotics
• Approximation algorithm
• Computational geometry
• Robot scheduling

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 = 2).

• 出版日期2014-12