3
$\begingroup$

A flow network is a directed graph in which each edge has a capacity. A flow through this network is an assignment of a value to each edge that is less or equal to the edge capacity, and such that the net incoming flow to every node balances with the net outcoming flux at that node. Two special nodes are exempted from this last restriction: the source (which can output a net non-zero flux) and the sink (which can receive a net non-zero flux).

There are algorithms to find the maximum net flow from source to sink in such a network (for example, Ford-Fulkerson algorithm).

I am looking for algorithms that generate pseudo-random admissible flows through such a network. Hopefully the space of admissible flows should be sampled as uniformly as possible. What methods are available here?

Improve this question
$\endgroup$
6
  • $\begingroup$ What properties should a "pseudo-random admissible flow" have? One easy way to get some kind of random flow: take a maximum flow, break it up into paths, and choose a random linear combination of these paths. Is this sufficient for your purposes? $\endgroup$
    – Peter Shor
    Commented Jul 24, 2014 at 13:24
  • $\begingroup$ @PeterShor The pseudo-random generator should explore as uniformly as possible the space of all flows. I think that starting with a maximum flow is very biased and many flows will never appear. $\endgroup$
    – a06e
    Commented Jul 24, 2014 at 13:28
  • 2
    $\begingroup$ What is "uniformly as possible"? I assume you want the flows to be close to the uniform distribution when restricted to the space of all admissible flows. You should probably add this criterion to your question. The word "pseudo-random" is quite vague, except in cryptographic applications. $\endgroup$
    – Peter Shor
    Commented Jul 24, 2014 at 13:54
  • 1
    $\begingroup$ idea: randomly change edge capacities to less than their max values, and find a maximum flow for that modified network. this paper also seems like it may have some relevant theory? Random Sampling in Cut, Flow, and Network Design Problems (1994) Karger $\endgroup$
    – vzn
    Commented Jul 24, 2014 at 20:39
  • 2
    $\begingroup$ The Metropolis algorithm might actually work well in this case. Choose a random "augmenting path" (so you can go along edges both backwards and forwards), figure out the largest amounts of flow you can push backwards and forwards along this path and still stay admissible, and choose a random value between these two extremes. Metropolis says this converges eventually to the uniform distribution on feasible flows. The only question is: how fast? $\endgroup$
    – Peter Shor
    Commented Jul 25, 2014 at 2:27

1 Answer 1

Reset to default
4
$\begingroup$

Not very practical, but you can sample from a the polytope of feasible flows using the well-known random walk techniques, see for example this classical paper by Kannan, Lovasz and Simonovits. These algorithms allow you to sample in polynomial time (in the dimension) from a distribution which is arbitrarily close to uniform in $L_1$ distance.

Improve this answer
$\endgroup$

Your Answer

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

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