¿Son prácticos algunos de los algoritmos de máximo flujo de última generación?

30

Para el problema del flujo máximo , parece haber una serie de algoritmos muy sofisticados, con al menos uno desarrollado tan recientemente como el año pasado. El flujo máximo de Orlin en tiempo O (mn) o mejor da un algoritmo que se ejecuta en O (VE).

Por otro lado, los algoritmos que veo más comúnmente implementados son (no pretendo haber hecho una búsqueda exhaustiva; esto es solo por observación casual):

  • Edmonds-Karp: ,O(Vmi2)
  • Push-relabel: u usando la selección de vértice FIFO,O(V2mi)O(V3)
  • Algoritmo de Dinic: O(V2mi) .

¿Los algoritmos con mejor tiempo de ejecución asintótico simplemente no son prácticos para los tamaños de problemas en el mundo real? Además, veo que los "árboles dinámicos" están involucrados en bastantes algoritmos; ¿Se utilizan alguna vez en la práctica?

Nota: esta pregunta se hizo originalmente en el desbordamiento de pila, aquí , pero me dijeron que encajaría mejor aquí.

EDITAR : Hice una pregunta relacionada sobre cs.stackexchange , específicamente sobre los algoritmos que usan árboles dinámicos (también conocidos como árboles de enlace cortado), que pueden ser de interés para las personas que siguen esta pregunta.

ds.algorithms graph-algorithms application-of-theory max-flow Rob Lachlan
fuente
1
hablando en un sentido general, si un algoritmo es "práctico" versus si está "implementado" es un poco diferente. idealmente, los autores lanzarían implementaciones de sus propios algoritmos, en cuyo caso generalmente sería "práctico" usarlos. En general, esto es más la excepción en la literatura TCS pero a menudo no es "práctico" "implementar" los algoritmos de otros autores que solo dan descripciones en documentos escritos en pseudocódigo, que a veces son significativamente o muy complejos ... la implementación exitosa incluye buenas pruebas de corrección, un proceso a veces desalentador ...
vzn
3
Andrew Goldberg solía tener una base de código muy agradable para diferentes variantes de flujo máximo en función de su trabajo de etiquetado de empuje. He usado el código en el pasado, y estaba muy limpio. Desafortunadamente, el sitio parece estar difunto.
Suresh Venkat
3
@vzn Me interesa saber si los algoritmos se prestan a la implementación práctica. Hay algoritmos que no lo hacen, y algunas personas han llamado a estos "algoritmos galácticos", porque tienen un excelente comportamiento asintótico, pero tienen tanta sobrecarga que actualmente no hay una ganancia práctica para implementarlos. (Los términos de orden inferior son importantes, después de todo). La multiplicación de matrices es el mejor ejemplo que puedo pensar, donde las mejores soluciones asintóticas nunca tienen un uso práctico. Tengo curiosidad por saber si Max Flow es una situación similar.
Rob Lachlan
55
si un algoritmo es "práctico" frente a si está "implementado" es un poco diferente. - Eso es correcto. Se puede implementar un algoritmo sin ser práctico, pero no al revés.
Jeff
2
Aquí está el código del estudio experimental de algoritmos de corte mínimo .
Austin Buchanan

Respuestas:

22

Soy uno de los autores del artículo vinculado anteriormente.

Solo quiero mencionar que usamos `` estado del arte '' para referirnos a algoritmos (con implementaciones disponibles públicamente) que funcionan bien en instancias de flujo máximo que surgen en la visión por computadora.

También me gustaría agregar que dentro de ese contexto estrecho (pero práctico), a menudo los algoritmos que funcionan bien son los que tienen pocas garantías teóricas. Por ejemplo, la referencia [5] de nuestro artículo (algoritmo Boykov-Kolmogorov) se usa ampliamente en la comunidad de visión por computadora, pero no tiene un límite de tiempo de ejecución fuertemente polimétrico.

Finalmente, en caso de que alguien esté interesado, los datos de nuestros experimentos están disponibles aquí: http://ttic.uchicago.edu/~dbatra/research/mfcomp/index.html

El código también estará disponible pronto.

Dhruv Batra
fuente
muy lindo que te hayas unido al grupo! ¡Bienvenido! Una pregunta sobre el artículo [desde el primer hallazgo]. Sería muy interesante escuchar más sobre el proceso de selección de algoritmos utilizados en el documento; no parecía dar más detalles al respecto. tal vez podría compartir algunas notas de fondo "detrás de escena" en algún lugar [por ejemplo, página web?] sobre qué algoritmos fueron seleccionados, cuáles fueron omitidos, por qué, qué desafíos hubo en la obtención / ejecución de implementaciones, qué piensa del más exótico algoritmos como el reciente de Orlins y sus perspectivas para una eventual implementación, etc.
vzn
7

Hay varias formas de responder esta pregunta, pero no necesariamente una respuesta consensuada. En general, los algoritmos que se han implementado y lanzado para distribución pública son "prácticos". sin embargo, algunos algoritmos que se han ideado pero aún no implementados pueden ser prácticos, pero "el jurado está fuera" de ellos, por así decirlo. **

Una buena estrategia para fines prácticos es buscar una encuesta. También para aquellos interesados ​​en algoritmos prácticos, los puntos de referencia contra datos del mundo real pueden ser una pauta excelente en cuanto a su comportamiento esperado del "mundo real".

Una encuesta de evaluación comparativa puede ser suficiente, pero errará en el lado de los algoritmos viables. Este es un análisis empírico reciente y exhaustivo de 14 algoritmos de flujo máximo "de última generación" comparados empíricamente con instancias de procesamiento de visión, donde el flujo máximo tiene muchas aplicaciones. "estado del arte" se toma para referirse a algoritmos "implementados".

[1] MaxFlow Revisited: una comparación empírica de algoritmos de Maxflow para problemas de visión densa por Verma y Batra, 2012

** algunos algoritmos teóricos están cada vez más en una categoría en la comunidad de TCS a la que se hace referencia informalmente como "galáctico", pero desafortunadamente, los autores de TCS actualmente no auto etiquetan sus algoritmos en esta categoría, y no hay criterios publicados o generalmente aceptados para algoritmos "galácticos", aunque hay referencias en blogs .

La practicidad en este sentido es posiblemente una nueva dimensión emergente para el estudio teórico. idealmente habría una encuesta de algoritmos de flujo máximo específicamente en este eje / criterio "práctico", pero es probable que no exista al momento de la escritura. es un concepto más recientemente reconocido / reconocido en TCS que aún no se ha formalizado completamente (a diferencia de, por ejemplo, la aceptación generalizada de los algoritmos P como "eficientes").

vzn
fuente
3
+1. No estoy seguro de por qué esto fue rechazado; Estoy leyendo el documento al que se vinculó, y ha sido muy útil para ver cuáles son los enfoques prácticos, al menos en ese dominio del problema.
Rob Lachlan
3
Robert Sedgewick dijo en una charla bastante reciente que el diseñador de algoritmos que no ejecuta experimentos corre el riesgo de perderse en la abstracción. La charla se trata de encontrar rutas en gráficos, y también está relacionada con maxflow. No responde la pregunta, pero puede ser interesante para alguien.
Juho
55
@Rob, la única parte relevante en esta respuesta es un enlace al documento y no hay mucho en la respuesta que explique por qué ese documento está vinculado en absoluto. Supongo que el OP encontró el enlace de Google y no lo ha leído. El resto de la respuesta son algunos comentarios generales y comentarios que indican la perspectiva personal de OP sobre cuestiones en las que él no es experto ni realmente relevante aquí. Las respuestas no son publicaciones de blog. Un enlace a un artículo relevante puede ser bueno como comentario, pero no responde. Esta es una mala respuesta si es una. Por eso lo he votado en contra.
Kaveh
2
@Kaveh lo suficientemente justo. El documento me pareció un indicador útil de lo que la gente considera algoritmos prácticamente útiles. Estoy de acuerdo en que queda mucho sin respuesta.
Rob Lachlan
3
Tampoco entiendo los votos negativos. No hay razón para creer que el póster NO leyó el artículo vinculado, y parece ser relevante. Puedo ver el deseo de no votar a favor, pero no a favor.
Suresh Venkat