Importante mejora de uno de los algoritmos básicos de la informática

El algoritmo de flujo maximal o flujo máximo es uno de los problemas más básicos de la informática. Se utiliza normalmente para planificar rutas aéreas, solucionar problemas de logística o crear redes de comunicaciones, además de ser un capítulo fundamental en todos los cursos de introducción a los algoritmos. Durante décadas constituyó un tema de investigación recurrente que ofrecía resultados importantes una o dos veces al año. Sin embargo, a medida que el problema empezó a ser ampliamente comprendido, el ritmo de las innovaciones comenzó a ralentizarse. Ahora, una nueva investigación del Instituto Tecnológico de Massachusetts (MIT), en colaboración con la Universidad de Yale y la Universidad del Sur de California, ha concluido con la primera gran mejora del algoritmo de flujo máximo en los diez últimos años, según un comunicado del MIT.

En términos generales puede decirse que este algoritmo se utiliza para calcular la cantidad máxima de “elementos” que pueden pasarse de un extremo a otro de una red, teniendo en cuenta las limitaciones de la capacidad de los enlaces de esa red. Esos “elementos” podrían ser, por ejemplo, los paquetes de datos que viajan a través de Internet o las cajas de mercancías que se trasladan por las carreteras. En estos casos las limitaciones en los enlaces harían referencia al ancho de banda de las conexiones a Internet o a la velocidad media del tráfico en las carreteras congestionadas.

De manera más técnica, el problema tiene que ver con lo que los matemáticos llaman grafos. Un grafo es un conjunto de puntos o vértices en el espacio, que están conectados por un conjunto de líneas o aristas. El esquema estándar de una red de comunicaciones es un grafo. En el problema de flujo máximo, uno de los vértices en el grafo es conocido como “fuente” (un nodo que no tiene arista entrante) y otro es designado “sumidero” (un nodo que no tiene aristas salientes) Cada una de las aristas tiene una capacidad asociada, es decir, una cantidad de “elementos” que pueden pasar por ellas.

La pregunta que trata de contestar el algoritmo es “¿cuál es la tasa mayor a la cual el material puede ser transportado de la fuente al sumidero sin violar ninguna restricción de capacidad?”. Es decir, el problema consiste en determinar la máxima capacidad de flujo que puede ingresar a través de la fuente y salir por el nodo de destino.

De grafos a matrices

Tradicionalmente, el procedimiento para obtener el flujo máximo de una red ha consistido en seleccionar cualquier trayectoria de la fuente al destino y asignar el flujo máximo posible en esa trayectoria. Y hacer esto repetidas veces, ya que en cada una de ellas solo se considera un camino a través del grafo. Sin embargo, la mejora introducida por el equipo estadounidense permite seleccionar, de una manera más inteligente, el orden en que estos caminos son explorados para reducir el tiempo en que se resuelve el problema.

El grupo de investigación, compuesto por Jonathan Kelner, profesor de Matemáticas Aplicadas en el MIT, Alexander Mandry, estudiante de posgrado en el Laboratorio de Informática e Inteligencia Artificial del MIT, el matemático Paul Christiano y los profesores Daniel Spielman y Shanghua Teng, de la Universidad de Yale y la USC respectivamente, ha adoptado un enfoque totalmente nuevo para el problema del flujo máximo. Su innovación consiste en representar el grafo como una matriz, en la que a cada nodo del grafo se le asigna una fila y una columna de la matriz. El número donde una fila y una columna coinciden representa la cantidad de cosas que pueden ser transferidas entre dos nodos.

En la rama de las matemáticas conocida como álgebra lineal, una fila de una matriz también se puede interpretar como una ecuación matemática. Las herramientas del álgebra lineal permiten la solución simultánea de todas las ecuaciones incorporadas por todas las filas de una matriz. Si se modifican los números de la matriz en repetidas ocasiones, se modifican las ecuaciones y los investigadores pueden evaluar eficazmente todo el grafo a la vez. Este enfoque, que Kelner tiene previsto describir hoy en una charla en el MIT, resulta ser más eficiente que probar caminos uno por uno.

Para demostrarlo, los investigadores plantean en el comunicado los resultados obtenidos con la siguiente fórmula: Si N es el número de nodos en un gráfico y L es el número de enlaces entre ellos, la ejecución de los algoritmos de flujo más rápidos hasta ahora era proporcional a (N + L)^(2/3). Sin embargo, la ejecución del nuevo algoritmo es proporcional a (N + L)^(4/3). Para una red como Internet, que tiene cientos de miles de millones de nodos, el nuevo algoritmo podría resolver el problema de flujo máximo cientos de veces más rápido que su predecesor.

En el mundo real estos grafos modelan redes de transporte y comunicación. Pero para Kelner, las posibilidades de aplicaciones prácticas del nuevo algoritmo van mucho más allá, desde el análisis de circuitos hasta el alineamiento de secuencias de ADN, pasando por el procesamiento digital de imágenes, entre otras.

La viabilidad inmediata del algoritmo, sin embargo, no es lo que más impresiona a John Hopcroft, profesor de Ingeniería y Matemática Aplicada en el centro de investigación de IBM en la Universidad de Cornell y ganador del Premio Turing, el más importante en Informática: «Mi predicción es que este marco particular va a ser aplicable a una amplia gama de problemas diferentes. Cuando hay un gran avance de esta naturaleza, por lo general, se suele formar una especialidad y en cuatro o cinco años, comienzan a surgir resultados interesantes”.