Investigadores de ETH Zúrich desarrollan el algoritmo de flujo más rápido posible

 (ethz.ch)
1 puntos por GN⁺ 2024-06-30 | 1 comentarios | Compartir por WhatsApp
  • El equipo de investigación de Rasmus Kyng en ETH Zurich desarrolló un algoritmo que calcula el problema de encontrar el flujo máximo en una red y minimizar los costos de transporte casi al límite matemático de velocidad
  • El nuevo algoritmo usa un enfoque de tiempo casi lineal que entrega la respuesta en una escala casi igual al tiempo necesario para leer los datos de la red, y puede aplicarse a cálculos de redes como ferrocarriles, carreteras, vías navegables e internet
  • En el pasado, si el número de conexiones era m, antes del año 2000 el nivel era de m^1.5 y en 2004 de m^1.33, pero el enfoque de Kyng reduce el tiempo de cálculo adicional después de leer los datos a un nivel prácticamente despreciable
  • El equipo también calcula en tiempo casi lineal la ruta más corta y el flujo máximo de costo mínimo en grafos incrementales, donde se agregan conexiones, y en grafos decrementales, donde se eliminan
  • Esto sienta las bases para recalcular rápidamente la ruta óptima en situaciones donde cambian redes reales, como el cierre y la reapertura parcial del Gotthard Base Tunnel o el deslizamiento de tierra en la autopista A13

Calcular problemas de flujo en redes casi al límite de velocidad

  • El algoritmo de flujo en redes del equipo de Rasmus Kyng aborda el problema de encontrar el máximo flujo posible en una red mientras minimiza el costo del transporte
  • Un ejemplo representativo es encontrar la ruta para mover la mayor cantidad posible de mercancías de Copenhagen a Milan de la forma más rápida y barata
  • Puede calcular flujos óptimos de bajo costo en redes con conexiones y capacidad, como ferrocarriles, carreteras, vías navegables e internet
  • La velocidad de cálculo se redujo hasta un nivel casi igual al tiempo que tarda una computadora en leer los datos de la red

Por qué es el algoritmo “más rápido”

  • Antes, el tiempo para calcular el flujo óptimo era mucho mayor que el tiempo necesario para procesar los datos de la red
  • Cuanto más grande y compleja era la red, más rápido crecía el tiempo de cálculo que el tamaño del problema
  • El enfoque de Kyng hace que el tiempo de cálculo y el tamaño de la red aumenten en la misma proporción
    • Si el número de conexiones de la red es m, solo leer los datos una vez toma un tiempo de m
    • Hasta antes del año 2000 no existía un algoritmo que calculase más rápido que m^1.5
    • En 2004, la cantidad de cálculo necesaria para resolver el problema se redujo hasta m^1.33
    • El algoritmo de Kyng reduce a un nivel despreciable el tiempo de cálculo adicional necesario para llegar a la solución después de leer los datos

Evaluación y expansión de los algoritmos de tiempo casi lineal

  • Hace dos años, el equipo de Kyng publicó un artículo con la demostración matemática de este concepto
  • Este tipo de algoritmo, casi óptimamente rápido, se conoce como algoritmo de tiempo casi lineal
  • Daniel A. Spielman comparó este algoritmo con un Porsche adelantando a un carruaje
  • Ese artículo recibió el Best Paper Award en el IEEE Annual Symposium on Foundations of Computer Science, FOCS, de 2022
  • Communications of the ACM también destacó esta investigación, y el equipo editorial de Quanta eligió el algoritmo de Kyng como uno de los 10 principales descubrimientos en ciencias de la computación de 2022

De redes estáticas a redes cambiantes

  • El algoritmo inicial se centró en redes fijas y estáticas con dirección definida en las conexiones
    • Las conexiones dirigidas tienen una estructura como la de las calles de un solo sentido en una red vial urbana
  • Después, el equipo desarrolló algoritmos para calcular el flujo óptimo también en redes que cambian gradualmente con el tiempo
  • Simon Meierhans presentó en Vancouver, en el Annual ACM Symposium on Theory of Computing, STOC, un nuevo algoritmo de tiempo casi lineal
    • Este algoritmo resuelve el problema de flujo máximo de costo mínimo en redes donde se agregan nuevas conexiones
  • En un segundo artículo aceptado para el IEEE Symposium on Foundations of Computer Science, FOCS, de octubre, desarrollaron un algoritmo que también maneja la eliminación de conexiones
  • Ambos algoritmos identifican la ruta más corta en redes donde las conexiones se agregan o eliminan

Ejemplos de cambios en redes reales

  • El Gotthard Base Tunnel de Suiza estuvo completamente cerrado desde el verano de 2023 y luego fue parcialmente reabierto
  • Parte de la autopista A13, una ruta alternativa principal del Gotthard Road Tunnel, fue destruida recientemente por un deslizamiento de tierra
  • Cuando ocurren estos cambios, las computadoras, los servicios de mapas en línea y los planificadores de rutas deben recalcular la conexión de menor costo y más corta entre Milan y Copenhagen
  • El nuevo algoritmo de Kyng calcula rutas óptimas en tiempo casi lineal incluso en redes donde se agregan o eliminan conexiones
  • Incluso cuando aparecen desvíos o nuevas rutas y se agregan conexiones, el tiempo de cálculo adicional sigue siendo prácticamente despreciable

Las dos estrategias previas y la nueva forma de combinarlas

  • El cálculo de flujo en redes requiere analizar la red varias veces para encontrar el flujo óptimo y la ruta de costo mínimo
  • En cada iteración se revisan variaciones como qué conexiones están abiertas, cuáles están cerradas y cuáles están congestionadas por haber alcanzado su límite de capacidad
  • Antes de Kyng, los científicos de la computación usaban principalmente una de dos estrategias
    • Modelo de red ferroviaria: en cada iteración se calcula una sección completa de la red donde cambió el flujo de tráfico
    • Modelo de red eléctrica: en cada iteración se calcula toda la red, pero usando valores promedio estadísticos para el flujo modificado de cada tramo a fin de acelerar el cálculo
  • El equipo de Kyng unió las ventajas de ambas estrategias para crear un nuevo enfoque combinado
  • Maximilian Probst Gutenberg considera que combinar muchos pasos de cálculo pequeños, eficientes y de bajo costo es mucho más rápido que usar unos pocos pasos grandes

Contexto histórico de los algoritmos de flujo

  • El problema de flujo en redes fue uno de los primeros problemas resueltos de forma sistemática mediante algoritmos en la década de 1950
  • Los algoritmos de flujo desempeñaron un papel importante para que la informática teórica se consolidara como un campo de investigación independiente
  • El conocido algoritmo de Lester R. Ford Jr. y Delbert R. Fulkerson también surgió en esa época
  • El algoritmo de Ford-Fulkerson resuelve eficientemente el problema de flujo máximo, que consiste en transportar por la red la mayor cantidad posible de mercancías sin superar la capacidad de cada ruta
  • Investigaciones posteriores mostraron que el problema de flujo máximo, el problema de costo mínimo y varios problemas de flujo en redes son casos especiales del más general problema de flujo de costo mínimo

Limitaciones de los algoritmos anteriores y el giro de 2004

  • Muchos algoritmos anteriores a la investigación de Kyng podían resolver eficientemente un problema específico, pero no eran lo suficientemente rápidos y resultaba difícil ampliarlos al problema más general de flujo de costo mínimo
  • John Edward Hopcroft, Richard Manning Karp y Robert Endre Tarjan, creadores de algoritmos de flujo pioneros en la década de 1970, recibieron el Turing Award
    • Karp lo recibió en 1985
    • Hopcroft y Tarjan lo recibieron en 1986
  • En 2004, Daniel Spielman, Shang-Hua Teng y, posteriormente, Samuel Daitch desarrollaron algoritmos que también ofrecían soluciones rápidas y eficientes para el problema de flujo de costo mínimo
  • Este grupo cambió la perspectiva del ferrocarril al flujo eléctrico en una red de energía
  • En una red eléctrica, el flujo de corriente puede desviarse parcialmente por conexiones donde ya está circulando otra corriente
  • Kyng no siguió directamente el poderoso enfoque algorítmico de Spielman para la red completa, sino que aplicó la idea de calcular rutas parciales al enfoque anterior de Hopcroft y Karp
  • El cálculo de rutas parciales en cada iteración desempeñó un papel importante para acelerar el cálculo del flujo completo

Nuevas herramientas matemáticas y estructuras de datos

  • El avance del equipo de ETH Zurich se basa no solo en nuevos algoritmos, sino también en el diseño de herramientas matemáticas que aceleran aún más el cálculo
  • El equipo desarrolló una nueva estructura de datos para organizar los datos de la red
  • Esta estructura de datos permite identificar muy rápidamente los cambios en las conexiones de la red
  • La identificación rápida de cambios funciona como un factor que incrementa la velocidad de la solución algorítmica
  • Los algoritmos de tiempo casi lineal y la nueva estructura de datos sientan las bases para resolver problemas muy grandes que antes no podían calcularse de manera eficiente

Artículos y materiales relacionados

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-06-30
Opiniones en Hacker News

  • Este algoritmo es asintóticamente casi lineal en el límite n -> inf
    Al final del video dicen que es difícil que cualquier implementación de este algoritmo supere a los algoritmos existentes en el mundo real
    https://cacm.acm.org/research/almost-linear-time-algorithms-...

    • ¿Entonces es otro algoritmo galáctico?
      https://en.wikipedia.org/wiki/Galactic_algorithm
    • Después de haber generado tantas expectativas al principio, resulta bastante anticlimático
    • Apenas vi el título me puse muy escéptico
      La expresión la velocidad más rápida posible es una afirmación realmente audaz
    • Otra pista en estos casos es que casi siempre se necesita una solución absolutamente óptima
      Muchas veces es mucho más práctico obtener el 99% de la calidad usando solo el 1% del tiempo

  • Curiosamente, la misma persona también trabaja en lograr que algoritmos solo teóricos funcionen bien en la práctica [1]
    Aunque parece que ese proceso toma otros 20 años más o menos. [1] se construyó sobre el avance teórico de 2004 [2], y según entiendo, estos algoritmos recién en 2024 empezaron a funcionar en la práctica. Si es así, podríamos esperar un algoritmo práctico de flujo de costo mínimo para 2044
    [1] https://arxiv.org/pdf/2303.00709
    [2] https://arxiv.org/abs/cs/0310051

  • Almost-Linear-Time Algorithm
    Pasar de O(mn) a O(m) significa sacar del cómputo a N, es decir, el número de vértices. ¿No suena demasiado bueno para ser cierto?

    • El factor constante será tan grande que, para entradas prácticas, será más lento que los algoritmos existentes con peor comportamiento asintótico
      Aun así, en teoría es un resultado genial

  • Las cifras brutas por sí solas muestran cuánto hemos avanzado. Antes de los años 2000, ningún algoritmo podía calcular más rápido que m1.5. Aquí, m significa la cantidad de conexiones de red que debe calcular la computadora, y solo leer una vez los datos de la red toma tiempo m. En 2004, la velocidad de cálculo necesaria para resolver este problema se redujo a m1.33. Con el algoritmo de Kyng, después de leer los datos de la red, el tiempo de cálculo “adicional” necesario para llegar a la solución ahora es despreciable.
    Me pregunto por qué el artículo original no explicó el avance de Kyng desde la perspectiva de la métrica m, a la que le da tanta importancia

  • A veces parece que nos perdemos por completo al tomar la complejidad como métrica
    Cada vez hay más algoritmos que optimizan la métrica de complejidad a niveles absurdos, pero que en la práctica no son útiles

    • Ese fenómeno existe desde hace décadas
      Después de que desaparecieron todos los logros fáciles, la investigación en algoritmos se convirtió en otro campo altamente especializado, y la mayoría de los papers no valen mucho el tiempo salvo para investigadores de áreas muy cercanas

  • Artículos relacionados: https://news.ycombinator.com/item?id=31149038 (40 comentarios)
    https://news.ycombinator.com/item?id=31675015 (72 comentarios)

  • ¿Dónde está el paper o el código?

  • Hay algo que me confunde aquí: o(n) parece una afirmación más fuerte que O(n)
    Porque todo algoritmo o(n) es O(n), pero lo inverso no es cierto. Además, si o(n) se aplica incluso a cualquier n pequeño, y O(n) solo aplica cuando n -> inf, ¿no debería este algoritmo poder aplicarse también a n pequeños? Entonces, ¿no debería ser lo contrario del algoritmo galáctico mencionado arriba? ¿Me estoy perdiendo algo?

    • La notación o pequeña sigue siendo una afirmación asintótica, así que no tiene por qué aplicarse a n pequeños
      La definición de f(n) = o(g(n)) es, a grandes rasgos, lim (n -> infinity) f(n)/g(n) = 0. En otras palabras, para n suficientemente grande, g crece más rápido que f
      Por ejemplo, una función como f(n) = 10n if n < 1000 else 1e1000 es o(n). Porque cuando n crece, 1e1000/n tiende a 0. Esta es una representación tipo Python de una función por tramos que crece exponencialmente hasta 101000 cuando n = 1000 y luego permanece constante
    • Si la complejidad de un algoritmo es 3↑↑64*n^0.999, ese algoritmo es o(n), pero puedes llamarlo tranquilamente algoritmo galáctico

  • Si no recuerdo mal, 3↑↑64 es el número de Graham

  • Malditos factores constantes, dan ganas de agitar el puño al cielo

  • En el resumen solo dice que el tiempo es m^(1+o(1))
    ¿Alguien sabe si en alguna parte aparece una cota superior más concreta?

    • Aquí o es o pequeña, así que captura un término cuyo “valor dividido por 1” tiende a 0 cuando m va al infinito
      https://de.m.wikipedia.org/wiki/Landau-Symbole
    • Significa que se pueden elegir constantes para acercarlo a O(m) tanto como se quiera
      Dicho de otro modo, es un esquema algorítmico que permite obtener un algoritmo que corre en tiempo O(m^ɛ) para cualquier ɛ>1
    • Esa es precisamente la cota superior concreta
      La o pequeña es una función que se acerca a 0 cuando n tiende al infinito, y se dice que es asintóticamente despreciable