3
$\begingroup$

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.

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ It seems to me it is not difficult to reduce it to the standard min cost max flow with min flow requirements. $\endgroup$
    – Kaveh
    Mar 24, 2014 at 19:09
  • $\begingroup$ 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. $\endgroup$
    – user22166
    Mar 25, 2014 at 14:25
  • $\begingroup$ Please state the question more formally, what do you mean by maximizing min cost flow? $\endgroup$
    – Kaveh
    Mar 25, 2014 at 18:34
  • 1
    $\begingroup$ @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. $\endgroup$
    – Kaveh
    Mar 25, 2014 at 23:20
  • 3
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Mar 26, 2014 at 1:10

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.