Flujo submodular

En la teoría de la optimización combinatoria , el flujo submodular es una clase general de problemas de optimización que incluye como casos especiales el problema del flujo de costo mínimo , la intersección de matroides y el problema de calcular un dijoin de peso mínimo en un grafo dirigido ponderado . Fue formulado originalmente por Jack Edmonds y Rick Giles, ^{[ 1 ]} y puede resolverse en tiempo polinomial . ^{[ 2 ] [ 3 ] [ 4 ]}

En el problema clásico de flujo de costo mínimo, la entrada es una red de flujo con capacidades dadas que especifican límites inferiores y superiores para la cantidad de flujo por arista, así como costos por unidad de flujo a lo largo de cada arista. El objetivo es encontrar un sistema de cantidades de flujo que cumpla con las capacidades en cada arista, obedezca la ley de Kirchhoff de que la cantidad total de flujo de entrada a cada vértice sea igual a la cantidad total de flujo de salida, y tenga un costo total mínimo. En el flujo submodular, también se proporciona una función de conjunto submodular sobre conjuntos de vértices del grafo. En lugar de obedecer la ley de Kirchhoff, se requiere que, para cada conjunto de vértices, el flujo excedente (la función que mapea el conjunto a su diferencia entre el flujo de entrada y el flujo de salida) sea como máximo el valor dado por la función submodular. ^{[ 4 ]}