Résumé - Heure de réveil améliorée pour le problème du tagage à gel euclidien

Heure de réveil améliorée pour le problème du tagage à gel euclidien

2025-07-22 06:37:10

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

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

Ce document présente des solutions améliorées pour le temps de réveil dans le Problème Euclidien du Taggelé (FTP) dans diverses dimensions et normes de distance. Le FTP implique d'activer un ensemble de robots endormis initialement aussi rapidement que possible, à partir d'un robot éveillé unique. L'objectif est de minimiser le temps de finition, ou le temps nécessaire pour activer le dernier robot, tout en prenant également en compte le ratio de réveil, qui est le temps maximum nécessaire pour activer un nombre quelconque de robots dans n'importe quelles positions primaires. ### Contributions : 1. **FTP dans (R2, ℓ2)** : Le document améliore la borne supérieure précédente de 4,62 pour le ratio de réveil à 4,31. Cela est réalisé par une analyse détaillée de la stratégie couronne, qui consiste à diviser le cercle unitaire en sections et à activer des robots dans ces sections. 2. **FTP dans (R3, ℓ1)** : Le document propose une nouvelle stratégie qui atteint un ratio de réveil de 12 pour l'FTP dans (R3, ℓ1), améliorant ainsi les bornes précédentes de 13 et de 13√. Cette stratégie implique de diviser la balle unitaire en sections et d'activer des robots dans ces sections. 3. **FTP dans (R3, ℓ2)** : Le document présente également une borne supérieure de 12,76 pour le ratio de réveil dans (R3, ℓ2), qui est une amélioration par rapport aux bornes précédentes de 13 et de 13√. Cela est réalisé par une approche similaire à celle de (R3, ℓ1), mais avec des considérations supplémentaires pour la géométrie de la sphère. ### Algorithmes : Le document propose plusieurs algorithmes basés sur la stratégie couronne, y compris : - **Algorithme à trois couronnes** : Cet algorithme implique d'activer un robot et d'utiliser ensuite ce robot pour activer deux couronnes, qui à leur tour activent d'autres robots. - **Algorithme à deux couronnes** : Cet algorithme est similaire à l'algorithme à trois couronnes mais implique l'activation simultanée de deux couronnes. - **Algorithme à quatre couronnes** : Cet algorithme est similaire à l'algorithme à deux couronnes mais implique l'activation simultanée de quatre couronnes. ### Résultats : Le document fournit des bornes supérieures pour le ratio de réveil dans diverses dimensions et normes de distance, et présente également un programme informatique qui évalue le temps de réveil pour une gamme d'instances d'entrée. Les résultats montrent que les algorithmes proposés fournissent des améliorations significatives par rapport aux approches précédentes. ### Conclusion : Ce document présente des solutions améliorées pour le temps de réveil dans le Problème Euclidien du Taggelé dans diverses dimensions et normes de distance. Les algorithmes et bornes proposés fournissent des insights précieux sur le problème et peuvent être utilisés pour concevoir des stratégies d'activation de robots plus efficaces.