El nuevo algoritmo puede optimizar drásticamente las soluciones para el problema de 'flujo máximo'

Encontrar la forma más eficiente de transportar artículos a través de una red como el sistema de carreteras de los EE. UU. O Internet es un problema que ha impuesto a los matemáticos e informáticos durante décadas.

Para abordar el problema, los investigadores han utilizado tradicionalmente un algoritmo de flujo máximo, también conocido como flujo máximo, en el que una red se representa como un gráfico con una serie de nodos, conocidos como vértices, y líneas de conexión entre ellos, llamadas bordes.

Dado que cada borde tiene una capacidad máxima, al igual que las carreteras o los cables de fibra óptica utilizados para transmitir información a través de Internet, dichos algoritmos intentan encontrar la forma más eficiente de enviar mercancías de un nodo en el gráfico a otro, sin exceder estas limitaciones.

Pero como el tamaño de redes como Internet ha crecido exponencialmente, a menudo resulta prohibitivo resolver estos problemas utilizando técnicas informáticas tradicionales, según Jonathan Kelner, profesor asociado de matemáticas aplicadas en el MIT y miembro del MIT Laboratorio de Informática e Inteligencia Artificial (CSAIL).

Entonces, en un artículo que se presentará en el Simposio ACM-SIAM sobre algoritmos discretos en Portland, Oregón, esta semana, Kelner y su colega Lorenzo Orecchia, un instructor de matemáticas aplicadas, junto con los estudiantes graduados Yin Tat Lee y Aaron Sidford, describirán un nuevo algoritmo teórico que puede reducir drásticamente el número de operaciones necesarias para resolver el problema del flujo máximo, lo que permite abordar incluso redes enormes como Internet o el genoma humano.

IMAGEN: CHRISTINE DANILOFF / CON

Recientemente ha habido una explosión en los tamaños de los gráficos que se están estudiando, dice Kelner. Por ejemplo, si quisiera enrutar el tráfico en Internet, estudiar todas las conexiones en Facebook o analizar datos genómicos, podría terminar fácilmente con gráficos con millones, miles de millones o incluso billones de bordes.

Los algoritmos de flujo máximo anteriores han abordado el problema en un borde, o una ruta, a la vez, dice Kelner. Entonces, por ejemplo, al enviar elementos del nodo A al nodo B, los algoritmos transmitirían algunos de los productos por una ruta, hasta que alcanzaran su capacidad máxima, y ​​luego comenzarían a enviar algunos por la siguiente ruta.

Muchos algoritmos anteriores, dice Kelner, encontrarían un camino desde el punto A al punto B, enviarían algo de flujo a lo largo de él y luego dirían: 'Dado lo que ya he hecho, ¿puedo encontrar otro camino por el que pueda enviar más?' Cuando uno necesita enviar flujo simultáneamente a lo largo de muchas rutas diferentes, esto conduce a una limitación intrínseca en la velocidad del algoritmo.

Pero en 2011 Kelner, el estudiante graduado de CSAIL Aleksander Madry, el estudiante de matemáticas Paul Christiano y sus colegas de la Universidad de Yale y la Universidad del Sur de California desarrollaron una técnica para analizar todos los caminos simultáneamente.

Los investigadores vieron el gráfico como una colección de resistencias eléctricas y luego imaginaron conectar una batería al nodo A y una tierra al nodo B, y permitir que la corriente fluya a través de la red. La corriente eléctrica no elige solo una ruta, enviará un poco de corriente a través de cada resistencia en la red, dice Kelner. Por lo tanto, analiza todo el gráfico a nivel mundial, estudiando muchos caminos al mismo tiempo.

Esto permitió que el nuevo algoritmo resolviera el problema de flujo máximo sustancialmente más rápido que los intentos anteriores.

Ahora, el equipo del MIT ha desarrollado una técnica para reducir aún más el tiempo de ejecución, lo que hace posible analizar incluso redes gigantes, dice Kelner.

A diferencia de los algoritmos anteriores, que han visto todas las rutas dentro de un gráfico como iguales, la nueva técnica identifica aquellas rutas que crean un cuello de botella dentro de la red. El algoritmo del equipo divide cada gráfico en grupos de nodos bien conectados y las rutas entre ellos crean cuellos de botella, dice Kelner.

Nuestro algoritmo determina qué partes del gráfico pueden enrutar fácilmente lo que necesitan y qué partes son los cuellos de botella. Esto le permite concentrarse en las áreas problemáticas y la estructura de alto nivel, en lugar de pasar mucho tiempo tomando decisiones sin importancia, lo que significa que puede usar su tiempo de manera mucho más eficiente, dice.

El resultado es un algoritmo casi lineal, dice Kelner, lo que significa que la cantidad de tiempo que lleva resolver un problema está muy cerca de ser directamente proporcional al número de nodos en la red. Entonces, si el número de nodos en el gráfico se multiplica por 10, la cantidad de tiempo se multiplicaría por algo muy cercano a 10, en lugar de multiplicarse por 100 o 1.000, dice. Esto significa que se escala esencialmente tan bien como cabría esperar con el tamaño de la entrada, dice.

Shanghua Teng, profesor de informática en la Universidad del Sur de California que no participó en el último artículo, dice que representa un gran avance en algoritmos de gráficos y software de optimización.

Este artículo, que es el ganador del premio al mejor artículo en la conferencia [ACM-SIAM], es el resultado de los esfuerzos sostenidos de Kelner y sus colegas en la aplicación de flujos eléctricos para diseñar algoritmos gráficos eficientes, dice Teng. El documento contiene una asombrosa variedad de contribuciones técnicas.

esconder