An XP Approximation Scheme for AFTP in 2D - Pedrosa, Lehilton Lelis Chaves; Silva, Lucas de Oliveira (Anais do Encontro de Teoria da Computação (ETC), 2025)
The Angular Freeze-Tag Problem (AFTP) concerns the distribution of mission data within a satellite swarm. In this scenario, satellites cannot be reached simultaneously via a single broadcast; instead, highly focused directional antennas are required. As a result, a satellite can only transmit when its antenna is oriented toward the recipient. This alignment may require reorienting the antenna, incurring a time cost proportional to the rotation angle. The objective is to minimize the makespan, i.e., the total distribution time. Approximating AFTP in the plane within a factor better than 5/3 is known to be NP-hard. We overcome this bound by introducing two new parameters: the smallest orientation change needed for a satellite’s antenna, starting from its initial position, to align with another satellite, and the total energy (rotation angle). This parametrization enables us to design a parameterized approximation scheme that runs in XP time. Furthermore, our approach extends to the AFTP variant that aims to minimize total energy instead of makespan.