# Complexity of a parametrized min-cost flow problem

Consider the following min-cost flow variant:

Input:

• a positively-weighted complete bipartite graph $G = (S, T, c)$ and extra vertices $s, t$
• edges from $s$ to $S$ and from $T$ to $t$.
• lower and upper capacity bounds $l_i, u_i$ on each edge $(s, s_i)$
• flow values $g_i$ for each edge $(t_i, t)$ with the constraint that $\sum_i g_i = 1$

For any flow assignment $f$ on the edges $(s, s_i)$ (note that by flow conservation $\sum_i f_i = 1$), let $\text{cost}(f)$ be the cost of a min-cost flow satisfying the upper and lower bounds.

Problem:

Find an $f$ satisfying all capacity constraints such that $\text{cost}(f)$ is maximized.

• It seems to me it is not difficult to reduce it to the standard min cost max flow with min flow requirements. Mar 24 '14 at 19:09
• I do not think this is correct. Note that in my question, we want to find $f(u,s_i)$ such that the minimal cost of the flow is maximized. Mar 25 '14 at 14:25
• Please state the question more formally, what do you mean by maximizing min cost flow? Mar 25 '14 at 18:34
• @maomao, no, it doesn't help much. I tried to put the information in the question in a more usual form. However the question is underspecified. Without knowing what is $G$ I don't think it can be shown to be even in NP. To me it looks that the author has some question and is trying to force it into some kind of flow problem but doesn't seem to be able to. Forget all details about the graph and the flow, they don't help because you are trying to maximize a function $G$ which you have not specified. You should spend more time formulating your question preciously. Mar 25 '14 at 23:20
• By the way, I think it works much better if you state the actual problem you are trying to solve as preciously as possible (what is the input? what should be the output? in mathematical terms) without forcing your idea about how to solve the question onto the statement of the question. Mar 26 '14 at 1:10

Note that $f$ and $g$ essentially define probability distributions over the $s_i$ and $t_i$. If we treat the $c(e)$ as a "length", then the mincost flow is basically the earthmover distance between the two distributions $f$ and $g$.
Now your maximization over $f$ is really saying: find the farthest neighbor to $g$ lying in a box defined over the simplex.
Formulating the problem this way suggests that you want some kind of projection from $g$ to the box.