Charla sobre flujo máximo con costo mínimo

Este jueves el entrenador Vladimir Antonio Charchabal impartió una charla sobre el tema flujo máximo con costo mínimo en un grafo. El entrenador comenzó recordando el algoritmo de flujo máximo como introducción, y a continuación pasó a enunciar el problema de flujo máximo con costo mínimo. Describió la modificación necesaria al algoritmo, y explicó cómo utilizarlo para resolver el problema de la asignación de trabajadores a tareas. Explicó que si lo que se desea es maximizar en lugar de minimizar, lo que se hace es poner los costos negativos en el grafo y ejecutar el mismo algoritmo.

Luego, a manera de ejemplo, indicó cómo utilizar el algoritmo para resolver el problema A Knights’ Tale. Luego se discutió entre los concursantes que una alternativa para resolver el problema es la asignación húngara, algoritmo que es más rápido pero que tiene limitantes y no se puede utilizar en todos los casos que el algoritmo de flujo máximo con costo mínimo, que es más general. Para finalizar, se explicó también cómo utilizar el algoritmo para resolver el problema Greedy island.

El entrenador escucha mientras los concursantes plantean dudas y sugerencias.