<p><em>this is too long for a comment, but it's not an answer</em></p>

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

<p>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$.</p>

<p>Now your maximization over $f$ is really saying: find the farthest neighbor to $g$ lying in a box defined over the simplex. </p>

<p>Formulating the problem this way suggests that you want some kind of projection from $g$ to the box. </p>

CC BY-SA 3.0
2014-03-27T13:35:44.073Z
2014-03-27T17:46:58.737Z
2014-03-27T17:46:58.737Z
Suresh Venkat
<p>Consider the following  min-cost flow variant:</p>

<p><strong>Input:</strong> </p>

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

<p>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. </p>

<p><strong>Problem</strong>:</p>

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

CC BY-SA 3.0
2014-03-24T19:09:36.503Z
It seems to me it is not difficult to reduce it to the standard min cost max flow with min flow requirements.
Kaveh
CC BY-SA 3.0
2014-03-25T14:25:11.283Z
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.
user22166
CC BY-SA 3.0
2014-03-25T18:34:19.910Z
Please state the question more formally, what do you mean by maximizing min cost flow?
Kaveh
CC BY-SA 3.0
2014-03-25T22:35:44.820Z
@Kaveh: I took my liberty to improve the question. Hope it helps.
maomao
CC BY-SA 3.0
2014-03-25T23:20:24.670Z
@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.
Kaveh
CC BY-SA 3.0
2014-03-26T01:10:32.080Z
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.
Kaveh
CC BY-SA 3.0
2014-03-26T08:01:04.770Z
Hmm, reading the question, I'm not sure what's the role of $cost(f)$? It seems to be defined and then left alone as we only care about $G$.
R B
CC BY-SA 3.0
2014-03-26T18:09:23.093Z
Now I have improved the question. Many thanks for the suggestion (I am new to this forum, so sorry for the mess). Could you please help me?
user22166
CC BY-SA 3.0
2014-03-27T12:54:51.670Z
I don't understand the "parametric" part. this appears to be a standard min cost flow. the "max/min" is not real, because the cost itself is not a minimization per se.
Suresh Venkat
CC BY-SA 3.0
2014-03-27T13:14:57.263Z
@Suresh Venkat: the cost is define as cost(f)=$\min_x{\sum_{e\in \{(s_i,t_j)∣1\leq i,j\leq n\}}x(e)c(e)}$; this is the minimal part. Usually when $f(s, s_i)$ and $g(t_i, t)$ are given, cost(f) is easy to compute; however, here I want to find $f(s, s_i)$ such that cost(f) is maxmized. Intuitively we have $max_f min_x x(e)c(e)$ (and $x$ depends on $f$): this is the max/min part.
user22166
CC BY-SA 3.0
2014-03-27T13:20:50.370Z
ah I see. so $f$ is fixed first, and then you find $f$.
Suresh Venkat
CC BY-SA 3.0
2014-03-27T15:37:50.140Z
I did a major rewrite of the problem defn. Hopefully it's clearer now.
Suresh Venkat
<cc.complexity-theory><graph-algorithms><max-flow>
Complexity of a parametrized min-cost flow problem
user22166
# Complexity of a parametrized min-cost flow problem

(Asked by: username_0 on 2014-03-24)

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.

**Tags:** cc.complexity-theory, graph-algorithms, max-flow

> **Comments:**
> **username_1**: It seems to me it is not difficult to reduce it to the standard min cost max flow with min flow requirements.  
> **username_0**: 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.  
> **username_1**: Please state the question more formally, what do you mean by maximizing min cost flow?  
> **username_2**: @username_1: I took my liberty to improve the question. Hope it helps.  
> **username_1**: @username_2, 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.  
> **username_1**: 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.  
> **username_3**: Hmm, reading the question, I'm not sure what's the role of $cost(f)$? It seems to be defined and then left alone as we only care about $G$.  
> **username_0**: Now I have improved the question. Many thanks for the suggestion (I am new to this forum, so sorry for the mess). Could you please help me?  
> **username_4**: I don't understand the "parametric" part. this appears to be a standard min cost flow. the "max/min" is not real, because the cost itself is not a minimization per se.  
> **username_0**: @username_4: the cost is define as cost(f)=$\min_x{\sum_{e\in \{(s_i,t_j)∣1\leq i,j\leq n\}}x(e)c(e)}$; this is the minimal part. Usually when $f(s, s_i)$ and $g(t_i, t)$ are given, cost(f) is easy to compute; however, here I want to find $f(s, s_i)$ such that cost(f) is maxmized. Intuitively we have $max_f min_x x(e)c(e)$ (and $x$ depends on $f$): this is the max/min part.  
> **username_4**: ah I see. so $f$ is fixed first, and then you find $f$.  
> **username_4**: I did a major rewrite of the problem defn. Hopefully it's clearer now.  

---

## 1 answers

### Answer by username_4 on 2014-03-27. Score: 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.


---

