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!

$\endgroup$

closed as unclear what you're asking by Dima Pasechnik, j.c., RP_, Mark Wildon, Neil Hoffman Nov 26 '18 at 15:15

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Uniformly in what sense? Different edges may have different capacities. $\endgroup$ – Dima Pasechnik Nov 22 '18 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 Nov 22 '18 at 15:53
  • $\begingroup$ One path maxed out example pic: imgur.com/a/U9cDDXz $\endgroup$ – Vili Volcini Nov 22 '18 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 Nov 22 '18 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 Nov 22 '18 at 16:24
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.

$\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.

$\endgroup$
  • $\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 Nov 23 '18 at 5:35
  • $\begingroup$ Thanks for comment. Will research those options :). $\endgroup$ – Vili Volcini Nov 24 '18 at 13:18

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