0
$\begingroup$

I am interested in using Max Flow algorithm. I want to simulate transfer of quantity. Anyway, I am unsure of some thing.

Does Max Flow algorithm produce uniformly distributed max flow?

I have provided example picture to show what I meant.

Black: edge capabilities Red: wrong, non-uniform results Green: correct, uniform results

max-flow-image-example

I do realize there are many types of Max Flow algorithms, so to add onto question, or to be more specific - which Max Flow algorithms produce uniform max flow and which don't?

Extra thing: I will use floating points (converted into integers) and then back. But I don't think this matters here.

Thanks in advance!

Improve this question
$\endgroup$
5
  • $\begingroup$ Uniformly in what sense? Different edges may have different capacities. $\endgroup$
    – Dima Pasechnik
    Commented Nov 22, 2018 at 15:22
  • $\begingroup$ Good point. I drew another picture. Lets say this way: uniform, if nothing is maxed out. If some edge is maxed out, then remaining quantity gets distributed equally to other non-maxed edges. Example picture: imgur.com/a/gZpRka2 I do not have "maxed out edge" scenario, but I shall draw some too. $\endgroup$
    – Vili Volcini
    Commented Nov 22, 2018 at 15:53
  • $\begingroup$ One path maxed out example pic: imgur.com/a/U9cDDXz $\endgroup$
    – Vili Volcini
    Commented Nov 22, 2018 at 15:56
  • 1
    $\begingroup$ It is a property of the problem that often the maximum is only reached on a path (with the edges outside it carrying no flow at all). That is, it's as non-uniform as it possibly could be. $\endgroup$
    – Dima Pasechnik
    Commented Nov 22, 2018 at 16:10
  • $\begingroup$ Many algorithms will always produce a basic solution (in the linear programming sense), thus an extreme point of the feasible region. This is, as Dima said, "as non-uniform as it possibly could be". $\endgroup$
    – Robert Israel
    Commented Nov 22, 2018 at 16:24

2 Answers 2

Reset to default
0
$\begingroup$

Typical max flow algorithms won't necessarily output a uniform flow.

The following paper defines a version of max flow called "balanced flow", and solve it in polynomial time.

Devanur, N. R., Papadimitriou, C. H., Saberi, A., & Vazirani, V. V. (2008). Market equilibrium via a primal--dual algorithm for a convex program. Journal of the ACM (JACM), 55(5), 22.

Improve this answer
$\endgroup$
-1
$\begingroup$

Apparently, it's feature of Max Flow to produce extreme results (or more like Linear Programming produces extreme results). So, it's not possible that Max Flow always produces uniform results.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Not being possible is a wild phrase. For example, after finding the max flow you can reduce each edge that a large amount of flow passed through it and see whether the solution changes. Or you can increase the capacities step by step from the start. $\endgroup$
    – Mohemnist
    Commented Nov 23, 2018 at 5:35
  • $\begingroup$ Thanks for comment. Will research those options :). $\endgroup$
    – Vili Volcini
    Commented Nov 24, 2018 at 13:18

Not the answer you're looking for? Browse other questions tagged .