Complejidad \ Solicitud de referencia para la variante del problema de flujo máximo

Question

En el problema de flujo de costo máximo estándar con capacidades de arco, el costo de usar un arco es proporcional al flujo a través del arco. Por ejemplo, si$f_{uv}$ es el flujo a través del arco $(u,v)$, entonces el costo de usar este arco viene dado por $\mathbf{c}_{uv} f_{uv}$, dónde $\mathbf{c}_{uv}$es un número real predefinido. Entonces, el objetivo que nos interesa maximizar es$\underset{(u, v) \in E}{\sum} \mathbf{c}_{uv} f_{uv}$, dónde $E$son los bordes en el gráfico. Puede suponer que el gráfico contiene una fuente y un nodo receptor, y que todos los flujos emanan de la fuente y drenan hacia el nodo receptor.

Considere la variante en la que el costo asociado con el uso del arco $(u,v)$en cambio, viene dado por: \ begin {cases} \ mathbf {c} _ {uv} f_ {uv} + \ mathbf {b} _ {uv}, \ text {if} f_ {uv}> 0, \\ 0, \ text {de lo contrario} \ end {cases} donde$\mathbf{b}_{uv}$ es un número positivo predefinido.

1. ¿Admite la variante del problema de flujo máximo una solución de tiempo polinomial?
2. Si no es así, ¿hay alguna referencia que pueda señalarme?

PD: Sé que la variante que mencioné se puede plantear fácilmente como MILP, sin embargo, estoy interesado en conocer los resultados estructurales y la complejidad de este problema.

Answer 1

Supongo que ni siquiera existe una solución óptima.

Quieres tener $\epsilon$-fluye por todos los bordes para cobrar todos los costos $b_{uv}$. Por otro lado, desea maximizar el flujo a través de los bordes con el mayor costo.$c_{uv}$. Esto conduce a la presión para tener$\epsilon$ tan pequeño como sea posible, mientras todavía $\epsilon > 0$. Tal$\epsilon$ no puede existir.