Nuevo algoritmo de flujo revoluciona cálculos de redes y bate récords de velocidad
MadridInvestigadores de ETH Zurich, liderados por Rasmus Kyng, han desarrollado el algoritmo más rápido para resolver problemas de flujo en redes. Este nuevo método se espera que revolucione la forma en que calculamos los flujos óptimos en redes.
El algoritmo de Kyng resuelve el problema del flujo máximo. Este algoritmo determina la manera más eficiente de mover mercancías a través de una red, minimizando los costos. Su aplicación es versátil, pudiendo utilizarse en redes de transporte y en internet.
A continuación, los puntos clave sobre el nuevo algoritmo:
- Calcula el flujo óptimo de red casi instantáneamente tras procesar los datos
- Funciona tanto para redes estáticas como para aquellas que cambian de manera incremental
- Gestiona tanto la adición como la eliminación de conexiones de red
- Reconocido como uno de los diez mayores descubrimientos en informática en 2022
- Ganó el Premio al Mejor Artículo en el Simposio Anual de Fundamentos de la Ciencia de la Computación (FOCS) de IEEE en 2022
En el pasado, encontrar las mejores rutas en las redes requería mucho tiempo. A medida que las redes crecían y se volvían más complejas, el tiempo necesario para calcularlas aumentaba aún más. Pero el método de Kyng asegura que el tiempo necesario para los cálculos y el tamaño de la red crezcan al mismo ritmo.
Hasta 2004, los mejores algoritmos podían calcular flujos en una red con una complejidad temporal proporcional al número de conexiones elevado a la potencia de 1.5. En 2004, esto mejoró a una complejidad temporal proporcional al número de conexiones elevado a la potencia de 1.33. Ahora, el algoritmo de Kyng reduce significativamente el tiempo de cálculo adicional.
El trabajo de Kyng está siendo mejorado. Los algoritmos actualizados ahora funcionan para redes que cambian con el tiempo. Calculan los mejores flujos rápidamente, incluso en redes con muchos cambios. Esto es esencial para redes del mundo real como sistemas de tráfico que están en constante cambio.
Simon Meierhans de ETH presentó un algoritmo rápido en el Simposio ACM sobre Teoría de la Computación en Vancouver. Este algoritmo resuelve el problema de flujo máximo con costo mínimo en redes que cambian gradualmente.
El equipo escribió otro artículo aceptado por FOCS donde desarrollaron un algoritmo para gestionar la eliminación de conexiones. Esto resulta útil en situaciones de la vida real como el cierre y la reapertura de rutas de tráfico.
El equipo de Kyng desarrolló un nuevo método mejorando técnicas anteriores. Utilizan muchos pasos pequeños en lugar de trabajar con grandes secciones. Este enfoque hace que los cálculos sean mucho más rápidos.
En la década de 1950, los investigadores comenzaron a resolver sistemáticamente problemas de flujo en redes. Durante este período, Lester R. Ford Jr. y Delbert R. Fulkerson desarrollaron algoritmos cruciales. Se centraron en el problema de máximo flujo, que consiste en mover bienes a través de una red de manera eficiente.
La mayoría de los algoritmos anteriores eran eficaces pero lentos. El algoritmo de Kyng es tanto eficaz como rápido. Antes de Kyng, los investigadores se centraban en modelos del sistema ferroviario o de la red eléctrica. El método de Kyng combina los mejores aspectos de ambos modelos.
El equipo desarrolló nuevas herramientas matemáticas para acelerar sus algoritmos. Implementaron un nuevo método para organizar datos de redes, lo que ayuda a detectar rápidamente cambios en las conexiones. Esto hace que el algoritmo sea mucho más rápido.
Investigadores de ETH Zurich desarrollan algoritmos rápidos que resuelven problemas complejos con gran eficiencia, transformando la manera en que las computadoras abordan tareas desafiantes.
Esta investigación es fundamental en el campo de la informática. Mejora la gestión de redes de datos grandes y dinámicas. Sus aplicaciones abarcan diversas áreas, como la biología y las redes sociales.
El estudio se publica aquí:
http://dx.doi.org/10.1145/3618260.3649745y su cita oficial - incluidos autores y revista - es
Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg. Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow. Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024 DOI: 10.1145/3618260.3649745
Compartir este artículo