Complexity of a parametrized min-cost flow problem

Question

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.

Answer 1

this is too long for a comment, but it's not an answer

One reformulation of your problem might prove to be useful in terms of finding related work.

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.