An XP Approximation Scheme for AFTP in 2D

• Lehilton Lelis Chaves Pedrosa Unicamp
• Lucas de Oliveira Silva Unicamp

DOI: https://doi.org/10.5753/etc.2025.8627

Abstract

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.

References

Arkin, E. M., Bender, M. A., Fekete, S. P., Mitchell, J. S. B., and Skutella, M. (2002). The Freeze-Tag Problem: How to Wake up a Swarm of Robots. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 568–577. Society for Industrial and Applied Mathematics.

Arkin, E. M., Bender, M. A., Fekete, S. P., Mitchell, J. S. B., and Skutella, M. (2006). The Freeze-Tag Problem: How to Wake Up a Swarm of Robots. Algorithmica, 46(2):193–221.

Arkin, E. M., Bender, M. A., and Ge, D. (2003). Improved approximation algorithms for the Freeze-Tag problem. In Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures - SPAA '03. ACM Press.

Beck, A. and Newman, D. J. (1970). Yet more on the linear search problem. Israel Journal of Mathematics, 8(4):419–429.

Brunner, J. and Wellman, J. (2020). An Optimal Algorithm for Online Freeze-Tag. In 10th International Conference on Fun with Algorithms (FUN 2021), volume 157 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:11. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.

Cygan, M., Fomin, F. V., Marx, D., Saurabh, S., Kowalik, L., Lokshtanov, D., and Pilipczuk, M. (2015). Parameterized Algorithms. Springer International Publishing, Cham, Switzerland.

Fekete, S. P. and Krupke, D. M. (2018). Beam it up, Scotty: Angular Freeze-Tag with directional antennas. EuroCG 2018 Berlin.

Krupke, D. M. (2022). Algorithm Engineering for Hard Problems in Computational Geometry. Phd thesis, Technische Universität Braunschweig.

Pedrosa, L. L. C. and de Oliveira Silva, L. (2023). Freeze–Tag is NP-Hard in 3D with L1 distance. In Proceedings of the XII Latin-American Algorithms, Graphs and Optimization Symposium. Elsevier BV.

Sztainberg, M. O., Arkin, E. M., Bender, M. A., and Mitchell, J. B. (2004). Theoretical and experimental analysis of heuristics for the “Freeze-Tag” robot awakening problem. IEEE Trans. Robot., 20(4):691–701.