El algoritmo de Rasmus Kyng revoluciona la optimización del flujo en redes complejas

MadridRasmus Kyng y su equipo de investigadores han logrado un avance significativo en los algoritmos de flujo de red. Han desarrollado un nuevo algoritmo que encuentra la manera más eficiente de mover cosas a través de una red mucho más rápido que antes. Este descubrimiento podría tener un impacto en muchos ámbitos, como el transporte, el tráfico de internet y las redes biológicas.

El novedoso algoritmo del equipo de Kyng disminuye los costos de transporte y aumenta el flujo de red. Este sistema puede leer rápidamente los datos de la red y calcular el flujo óptimo, lo cual representa una mejora considerable ya que los algoritmos anteriores requerían mucho más tiempo para procesar conforme la red se expandía.

Esta es la razón por la que esto marca un hito:

• El algoritmo proporciona soluciones en el momento que una computadora lee los datos de la red.
• El tiempo de computación y el tamaño de la red aumentan al mismo ritmo.
• Supera significativamente a los algoritmos anteriores.

Anteriormente, encontrar el mejor flujo en redes grandes requería mucho tiempo. Kyng resolvió este problema haciendo el proceso rápido y eficiente. El nuevo método utiliza numerosas pequeñas y rápidas cálculos en lugar de unos pocos grandes. Este cambio es lo que lo hace mucho más rápido.

A principios de la década de 2000, los algoritmos más rápidos tardaban aproximadamente m^1.5, donde m es el número de conexiones en la red. Para 2004, este tiempo se redujo a m^1.33. El nuevo algoritmo de Kyng ha logrado que el tiempo de cálculo adicional sea casi insignificante, convirtiéndose en el algoritmo más rápido para estos problemas.

Lea también:

Ayer · 23:05

Los vikingos: maestros del comercio ártico de marfil

El equipo de Kyng mejoró sus métodos, creando algoritmos casi instantáneos para redes en constante cambio. Estos algoritmos pueden adaptarse a redes con conexiones nuevas o ausentes. El miembro del equipo, Simon Meierhans, presentó un nuevo algoritmo para cambios incrementales en el Simposio Anual de la ACM sobre Teoría de la Computación en Vancouver. Este algoritmo actualiza las nuevas conexiones casi de inmediato.

Un estudio reciente, aceptado por FOCS en octubre, presentó un algoritmo para gestionar nuevas y eliminadas conexiones. Esto permite ajustes de rutas rápidos y eficientes, útiles en situaciones reales como el manejo de cierres de carreteras o la búsqueda de rutas alternativas alrededor de accidentes.

Las rápidas computaciones de Kyng presentan un nuevo método para manejar redes complejas. Los algoritmos anteriores analizaban secciones de la red o la red completa utilizando valores promedio. El método de Kyng fusiona estas dos estrategias para mejorar la eficiencia.

Nuevas herramientas matemáticas han sido desarrolladas para acelerar estos algoritmos. Una de ellas es una nueva forma de organizar datos de red más rápidamente. Esto permite detectar cambios en la red con más agilidad, acelerando los cálculos.

Este trabajo ha resuelto muchos problemas antiguos y ha mejorado la manera en que las computadoras manejan tareas complejas. Podría ayudar a hacer más eficientes sistemas como el transporte, las comunicaciones y la biología, lo que podría derivar en aplicaciones mejores y más rápidas en diversas áreas.