Nouvelle avancée : un algorithme révolutionnaire bat des records de vitesse pour les flux de réseau

ParisDes chercheurs de l'ETH Zurich, dirigés par Rasmus Kyng, ont élaboré l'algorithme le plus rapide pour résoudre les problèmes de flux dans les réseaux. Cette méthode innovante devrait transformer notre manière de calculer les flux optimaux au sein des réseaux.

L'algorithme de Kyng résout le problème de flot maximum. Il détermine la manière la plus efficace de transporter des biens à travers un réseau tout en minimisant les coûts. Cette méthode peut s'appliquer à divers types de réseaux tels que les systèmes de transport et internet.

Points clés concernant le nouvel algorithme :

• Optimise instantanément les flux de réseau après lecture des données
• Compatible avec des réseaux statiques et évolutifs
• S'adapte à l'ajout et à la suppression de connexions réseau
• Classé parmi les dix plus grandes découvertes en informatique de 2022
• Lauréat du Best Paper Award 2022 au symposium annuel de l'IEEE sur les fondements de l'informatique (FOCS)

Par le passé, trouver les meilleurs chemins dans les réseaux prenait beaucoup de temps. Avec l'augmentation de la taille et de la complexité des réseaux, le temps de calcul s'allongeait davantage. Cependant, la méthode Kyng garantit que le temps de calcul et la taille du réseau augmentent au même rythme.

Jusqu’en 2004, les meilleurs algorithmes pouvaient calculer les flux dans un réseau avec une complexité temporelle proportionnelle au nombre de connexions élevé à la puissance de 1,5. En 2004, cette complexité fut améliorée à une puissance de 1,33. Aujourd'hui, l’algorithme de Kyng réduit encore plus significativement le temps de calcul supplémentaire.

Le travail de Kyng connaît des améliorations. Les algorithmes mis à jour fonctionnent désormais pour des réseaux évoluant dans le temps. Ils calculent rapidement les flux optimaux, même dans les réseaux avec de nombreuses modifications. Ceci est crucial pour des réseaux réels comme les systèmes de circulation en perpétuelle évolution.

Simon Meierhans de l'ETH a présenté un algorithme rapide au Symposium ACM sur la théorie de l'informatique à Vancouver. Cet algorithme traite le problème du flux maximal à coût minimal pour les réseaux qui changent progressivement.

Lisez aussi:

Aujourd'hui · 15:52

Optimiser la santé des récifs par des compensations

L'équipe a publié un nouvel article, accepté à FOCS, décrivant un algorithme permettant de gérer la suppression des liaisons. Cette méthode est utile pour gérer des situations réelles comme la fermeture et la réouverture des routes.

L'équipe de Kyng a développé une nouvelle méthode en améliorant les techniques précédentes. Ils utilisent de nombreuses petites étapes plutôt que de traiter de grandes sections. Cette approche permet d'accélérer considérablement les calculs.

Dans les années 1950, des chercheurs ont commencé à résoudre systématiquement les problèmes de flux dans les réseaux. C'est à cette époque que Lester R. Ford Jr. et Delbert R. Fulkerson ont mis au point des algorithmes essentiels. Ils se sont attaqués au problème du flot maximum, qui consiste à acheminer des marchandises à travers un réseau de manière efficace.

La plupart des algorithmes antérieurs étaient efficaces mais lents. L'algorithme de Kyng est à la fois efficace et rapide. Avant Kyng, les chercheurs se concentraient soit sur les modèles ferroviaires, soit sur les réseaux électriques. La méthode de Kyng combine les meilleurs aspects des deux modèles.

L'équipe a développé de nouveaux outils mathématiques pour accélérer leurs algorithmes. Ils ont innové dans l'organisation des données de réseau, facilitant ainsi la détection rapide des modifications des connexions. Cette approche rend l'algorithme bien plus rapide.

Des chercheurs de l'ETH Zurich ont mis au point de nouveaux algorithmes extrêmement rapides. Ces algorithmes permettent de résoudre rapidement des problèmes complexes et révolutionnent la manière dont les ordinateurs traitent les tâches les plus ardues.

Cette recherche joue un rôle crucial en informatique. Elle améliore notre manière de gérer les réseaux de données volumineux et dynamiques. Ses applications sont variées et s'étendent à des domaines comme la biologie et les réseaux sociaux.