Is anyone aware of a max flow algorithm where the edges are conditioned upon one another?
Meaning if I send f units of flow from vertex a --> b, then I have to send .5*f* unit from a --> c.
$\begingroup$
$\endgroup$
1
-
6$\begingroup$ You could express maxflow problem as a linear programming problem. You could add constraints of the form you mentioned to the linear program and then solve it via a general purpose LP solver. $\endgroup$– Chandra ChekuriMar 28, 2013 at 21:43
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The problem you describe is a generalization of the equal flow problem first proposed by Sahni. In addition to the flow network, the input specifies several disjoint sets $R_1, R_2, \dots, R_k$ of arcs; the goal is to find a maximum flow such that for each $i$, all arcs in $R_i$ have the same flow value.
While the fractional version of the equal flow problem can be solved in polynomial time by linear programming, the integer version is NP-hard, even if the capacity of each arc is $1$ and all arcs in each set $R_i$ leave the same vertex $v_i$. Worse, Meyers and Schulz recently proved that there is no polynomial-time $2^{n(1-\epsilon)}$-approximation algorithm, for any fixed $\epsilon>0$, unless $P=NP$. (The integrality gap of the fractional LP can be arbitrarily large.)
- Carol Meyers and Andreas Schulz. Integer equal flows. Operations Research Letters 37(4):245-249, 2009.
