Resumen - Tiempo de Despertar Mejorado para el Problema del Congelamiento Euclidiano

Tiempo de Despertar Mejorado para el Problema del Congelamiento Euclidiano

2025-07-22 06:37:10

{"Sharareh Alipour","Arash Ahadi","Kajal Baghestani"}

{cs.CG,cs.DC,cs.RO}

Este documento presenta soluciones mejoradas para el tiempo de activación en el Problema Euclidiano del Etiquetado con Congelación (FTP) en diversas dimensiones y normas de distancia. El FTP implica activar un conjunto de robots inicialmente en reposo tan rápidamente como sea posible, comenzando con un solo robot despierto. El objetivo es minimizar el tiempo de ejecución, o el tiempo requerido para activar el último robot, considerando también la relación de activación, que es el tiempo máximo necesario para activar cualquier número de robots en cualquier posición primaria. ### Contribuciones: 1. **FTP en (R2, ℓ2)**: El documento mejora el límite superior anterior de 4.62 para la relación de activación a 4.31. Esto se logra mediante un análisis detallado de la estrategia de corona, que implica dividir la circunferencia unitaria en secciones y activar robots dentro de esas secciones. 2. **FTP en (R3, ℓ1)**: El documento propone una nueva estrategia que alcanza una relación de activación de 12 para el FTP en (R3, ℓ1), mejorando los límites superiores anteriores de 13 y 13√. Esta estrategia implica dividir la esfera unitaria en secciones y activar robots dentro de esas secciones. 3. **FTP en (R3, ℓ2)**: El documento también presenta un límite superior de 12.76 para la relación de activación en (R3, ℓ2), que es una mejora sobre los límites superiores anteriores de 13 y 13√. Esto se logra mediante un enfoque similar al de (R3, ℓ1), pero con consideraciones adicionales sobre la geometría de la esfera. ### Algoritmos: El documento propone varios algoritmos basados en la estrategia de corona, incluyendo: - **Algoritmo de tres coronas**: Este algoritmo implica activar un robot y luego usar ese robot para activar dos coronas, que a su vez activan otros robots. - **Algoritmo de dos coronas**: Este algoritmo es similar al de tres coronas pero implica activar dos coronas simultáneamente. - **Algoritmo de cuatro coronas**: Este algoritmo es similar al de dos coronas pero implica activar cuatro coronas simultáneamente. ### Resultados: El documento proporciona límites superiores para la relación de activación en diversas dimensiones y normas de distancia, y también presenta un programa de computadora que evalúa el tiempo de activación para una gama de instancias de entrada. Los resultados muestran que los algoritmos propuestos proporcionan mejoras significativas sobre los enfoques anteriores. ### Conclusión: Este documento presenta soluciones mejoradas para el tiempo de activación en el Problema Euclidiano del Etiquetado con Congelación en diversas dimensiones y normas de distancia. Los algoritmos propuestos y los límites superiores proporcionan valiosas insinuaciones sobre el problema y pueden ser utilizados para diseñar estrategias de activación de robots más eficientes.