ETH Zurich: Flujo instantáneo, el algoritmo más rápido jamás creado.

En un avance innovador que evoca a Lucky Luke, el hombre que dispara más rápido que su propia sombra, Rasmus Kyng y su equipo han desarrollado un algoritmo ultrarrápido que promete transformar todo un campo de investigación. El trabajo pionero del equipo de Kyng implica lo que se conoce como un algoritmo de flujo de red, que aborda la cuestión de cómo lograr el flujo máximo en una red minimizando al mismo tiempo los costes de transporte.

Imagina que estás utilizando la red de transporte europea y buscas la ruta más rápida y barata para mover la mayor cantidad de mercancías posible desde Copenhague hasta Milán. El algoritmo de Kyng puede aplicarse en estos casos para calcular el flujo de tráfico óptimo y de menor coste para cualquier tipo de red, ya sea ferroviaria, por carretera, por agua o por internet. Su algoritmo realiza estos cálculos tan rápido que puede entregar la solución en el mismo instante en que un ordenador lee los datos que describen la red.

Cálculos tan rápidos como la red es grande

Antes de Kyng, nadie había logrado hacer eso, aunque los investigadores llevan trabajando en este problema desde hace unos 90 años. Anteriormente, se tardaba significativamente más tiempo en calcular el flujo óptimo que en procesar los datos de la red. Y a medida que la red se hacía más grande y compleja, el tiempo de cálculo necesario aumentaba mucho más rápido, en términos comparativos, que el tamaño real del problema computacional. Es por eso que también vemos problemas de flujo en redes que son demasiado grandes para que un ordenador pueda incluso calcularlas.

El enfoque de Kyng elimina este problema: utilizando su algoritmo, el tiempo de cálculo y el tamaño de la red aumentan al mismo ritmo, un poco como hacer una caminata y mantener siempre el mismo ritmo, sin importar cuán empinada sea la senda. Un vistazo a las cifras brutas muestra cuánto hemos avanzado: hasta el cambio de milenio, ningún algoritmo logró calcular más rápido que m^1.5, donde m representa el número de conexiones en una red que el ordenador tiene que calcular, y simplemente leer los datos de la red una vez toma m tiempo. En 2004, la velocidad de cálculo necesaria para resolver el problema se redujo con éxito a m^1.33. Utilizando el algoritmo de Kyng, el tiempo de cálculo “adicional” necesario para llegar a la solución después de leer los datos de la red ahora es insignificante.

Como un Porsche compitiendo con un carruaje tirado por caballos

Los investigadores del ETH Zurich han desarrollado así lo que es, en teoría, el algoritmo de flujo de red más rápido posible. Hace dos años, Kyng y su equipo presentaron la prueba matemática de su concepto en un artículo innovador. Los científicos se refieren a estos novedosos algoritmos, casi óptimamente rápidos, como “algoritmos casi lineales”, y la comunidad de científicos informáticos teóricos respondió al avance de Kyng con una mezcla de asombro y entusiasmo.

El director de doctorado de Kyng, Daniel A. Spielman, profesor de Matemáticas Aplicadas e Informática en Yale y él mismo pionero y decano en este campo, comparó el algoritmo “absurdamente rápido” con un Porsche adelantando a carruajes tirados por caballos. Además de ganar el premio al mejor artículo de 2022 en el Simposio anual IEEE sobre Fundamentos de la Ciencia Informática (FOCS), su artículo también fue destacado en la revista de informática Communications of the ACM, y los editores de la revista de divulgación científica Quanta nombraron el algoritmo de Kyng como uno de los diez mayores descubrimientos en informática en 2022.

Los investigadores del ETH Zurich han refinado desde entonces su enfoque y han desarrollado otros algoritmos casi lineales. Por ejemplo, el primer algoritmo seguía centrándose en las redes fijas y estáticas cuyas conexiones son dirigidas, lo que significa que funcionan como calles de un solo sentido en las redes de carreteras urbanas. Los algoritmos publicados este año ahora también son capaces de calcular flujos óptimos para redes que cambian incrementalmente con el tiempo. La computación ultrarrápida es un paso importante para abordar redes altamente complejas y ricas en datos que cambian de forma dinámica y muy rápida, como las moléculas o el cerebro en biología, o las amistades humanas.

Algoritmos ultrarrápidos para redes cambiantes

El jueves, Simon Meierhans, miembro del equipo de Kyng, presentó un nuevo algoritmo casi lineal en el Simposio Anual ACM sobre Teoría de la Computación (STOC) en Vancouver. Este algoritmo resuelve el problema del flujo máximo de coste mínimo para redes que cambian incrementalmente a medida que se añaden nuevas conexiones. Además, en un segundo artículo aceptado por el Simposio IEEE sobre Fundamentos de la Ciencia Informática (FOCS) en octubre, los investigadores del ETH han desarrollado otro algoritmo que también maneja la eliminación de conexiones.

En concreto, estos algoritmos identifican las rutas más cortas en redes donde se añaden o eliminan conexiones. En las redes de tráfico del mundo real, algunos ejemplos de estos cambios en Suiza son el cierre completo y posterior reapertura parcial del túnel de base del San Gotardo en los meses posteriores al verano de 2023, o el reciente deslizamiento de tierra que destruyó parte de la autopista A13, que es la principal ruta alternativa al túnel de carretera del San Gotardo.

Ante estos cambios, ¿cómo calcula un ordenador, un servicio de mapas online o un planificador de rutas la conexión de menor coste y más rápida entre Milán y Copenhague? Los nuevos algoritmos de Kyng también calculan la ruta óptima para estas redes que cambian de forma incremental o decremental en tiempo casi lineal, tan rápido que el tiempo de cálculo para cada nueva conexión, ya sea añadida a través de un reencaminamiento o la creación de nuevas rutas, vuelve a ser insignificante.

Pero, ¿qué es exactamente lo que hace que el enfoque de Kyng para los cálculos sea mucho más rápido que cualquier otro algoritmo de flujo de red? En principio, todos los métodos computacionales se enfrentan al reto de tener que analizar la red en múltiples iteraciones para encontrar el flujo óptimo y la ruta de menor coste. Al hacerlo, recorren cada una de las diferentes variantes de qué conexiones están abiertas, cerradas o congestionadas porque han alcanzado su límite de capacidad.

¿Calcular el todo? ¿O sus partes?

Antes de Kyng, los científicos informáticos tendían a elegir entre dos estrategias claves para resolver este problema. Una de ellas se modelaba en la red ferroviaria e implicaba calcular toda una sección de la red con un flujo de tráfico modificado en cada iteración. La segunda estrategia, inspirada en los flujos de potencia en la red eléctrica, computa la red completa en cada iteración, pero utiliza valores medios estadísticos para el flujo modificado de cada sección de la red con el fin de hacer el cálculo más rápido.

El equipo de Kyng ha unido ahora las ventajas respectivas de estas dos estrategias para crear un nuevo enfoque combinado radical. “Nuestro enfoque se basa en muchos pasos computacionales pequeños, eficientes y de bajo coste, que, tomados en conjunto, son mucho más rápidos que unos pocos grandes”, dice Maximilian Probst Gutenberg, profesor y miembro del grupo de Kyng, que desempeñó un papel clave en el desarrollo de los algoritmos casi lineales.

Una breve mirada a la historia de esta disciplina añade una dimensión adicional a la importancia del avance de Kyng: los problemas de flujo en las redes fueron de los primeros en resolverse sistemáticamente con la ayuda de algoritmos en la década de 1950, y los algoritmos de flujo desempeñaron un papel importante en el establecimiento de la informática teórica como campo de investigación por derecho propio. El conocido algoritmo desarrollado por los matemáticos Lester R. Ford Jr. y Delbert R. Fulkerson también proviene de este período. Su algoritmo resuelve eficientemente el problema del flujo máximo, que busca determinar cómo transportar la mayor cantidad de mercancías posible a través de una red sin exceder la capacidad de las rutas individuales.

Rápido y de amplio alcance

Estos avances demostraron a los investigadores que el problema del flujo máximo, el problema del coste mínimo (problema de transbordo o transporte) y muchos otros problemas importantes de flujo de red pueden considerarse como casos especiales del problema general del flujo de coste mínimo. Antes de la investigación de Kyng, la mayoría de los algoritmos solo podían resolver uno de estos problemas de forma eficiente, aunque no podían hacerlo con particular rapidez, ni podían ampliarse al problema más amplio del flujo de coste mínimo. Lo mismo ocurre con los algoritmos de flujo pioneros de la década de 1970, por los que los informáticos teóricos John Edward Hopcroft, Richard Manning Karp y Robert Endre Tarjan recibieron cada uno un premio Turing, considerado el “Premio Nobel” de la informática. Karp recibió el suyo en 1985; Hopcroft y Tarjan ganaron el suyo en 1986.

Cambio de perspectiva de los ferrocarriles a la electricidad

No fue hasta 2004 que los matemáticos e informáticos Daniel Spielman y Shang-Hua Teng, y más tarde Samuel Daitch, lograron escribir algoritmos que también proporcionaban una solución rápida y eficiente al problema del flujo de coste mínimo. Fue este grupo el que cambió el enfoque hacia los flujos de potencia en la red eléctrica. Su cambio de perspectiva de los ferrocarriles a la electricidad llevó a una distinción matemática clave: si un tren es desviado en la red ferroviaria porque una línea está fuera de servicio, la siguiente mejor ruta según el horario ya puede estar ocupada por un tren distinto. En la red eléctrica, es posible que los electrones que componen un flujo de potencia se desvíen parcialmente a una conexión de red por la que ya está fluyendo otra corriente. Por lo tanto, a diferencia de los trenes, la corriente eléctrica puede, en términos matemáticos, “mover”se parcialmente a una nueva conexión.

Este reencaminamiento parcial permitió a Spielman y sus colegas calcular estos cambios de ruta mucho más rápido y, al mismo tiempo, recalcular toda la red después de cada cambio. “Rechazamos el enfoque de Spielman de crear los algoritmos más potentes que pudiéramos para toda la red”, dice Kyng. “En cambio, aplicamos su idea de cálculo parcial de rutas a los enfoques anteriores de Hopcroft y Karp.” Este cálculo de rutas parciales en cada iteración desempeñó un papel importante en la aceleración del cálculo de flujo general.

Un punto de inflexión en los principios teóricos

Gran parte del progreso de los investigadores del ETH Zurich se reduce a la decisión de ampliar su trabajo más allá del desarrollo de nuevos algoritmos. El equipo también utiliza y diseña nuevas herramientas matemáticas que aceleran aún más sus algoritmos. En particular, han desarrollado una nueva estructura de datos para organizar los datos de red; esto permite identificar cualquier cambio en una conexión de red de forma extremadamente rápida; esto, a su vez, ayuda a que la solución algorítmica sea tan increíblemente rápida. Con tantas aplicaciones alineadas para los algoritmos casi lineales y para herramientas como la nueva estructura de datos, la espiral de innovación general podría pronto estar girando mucho más rápido que antes.

Sin embargo, sentar las bases para resolver problemas muy grandes que antes no podían calcularse de forma eficiente es sólo uno de los beneficios de estos algoritmos de flujo significativamente más rápidos, porque también cambian la forma en que los ordenadores calculan las tareas complejas en primer lugar. “En la última década, ha habido una revolución en los fundamentos teóricos para obtener algoritmos demostrablemente rápidos para problemas fundamentales de la informática teórica”, escribe un grupo internacional de investigadores de la Universidad de California, Berkeley, que incluye entre sus miembros a Rasmus Kyng y Deeksha Adil, investigadora del Instituto de Estudios Teóricos del ETH Zurich.