10
$\begingroup$

Motivation: In standard augmenting path maxflow algorithms, the inner loop requires finding paths from source to sink in a directed, weighted graph. Theoretically, it is well-known that in order for the algorithm to even terminate when there are irrational edge capacities, we need to put restrictions on the paths that we find. The Edmonds-Karp algorithm, for example, tells us to find shortest paths.

Empirically, it has been observed that we might also want to find fat (is there a better term for this?) paths. For example, when using capacity scaling, we find shortest paths that can bear at least $\epsilon$ amount of flow. There is no restriction on how long the path can be. When we can no longer find any paths, we decrease $\epsilon$ and repeat.

I am interested in optimizing the choice of augmenting paths for a very specific application of max-flow, and I want to explore this tradeoff between short and fat paths. (Note: it is not necessary for me to always solve the problem. I am most interested in finding the largest lower bound on flow in the shortest amount of wall time.)

Question: Is there a standard way to interpolate between the shortest path approach and the capacity-scaling approach? That is, is there an algorithm for finding paths that are both short and fat, where ideally some parameter would control how much length in the path we are willing to trade off for fatness? At the extremes, I'd like to be able to recover shortest paths on one end and capacity scaling-style paths on the other.

$\endgroup$
  • 3
    $\begingroup$ Note that if you try to optimize both shortness and fatness at the same time, you enter the realms of multicriteria optimizsation which means in most cases NP-hardness. $\endgroup$ – Raphael Oct 12 '10 at 9:18
  • $\begingroup$ @dan x: I'm aware of capacity scaling algorithms for max flow, but not the specific one you're describing. Do you have a reference (conference paper, journal article, scribed lecture(s), etc.) describing your version of capacity scaling in detail? I'm curious if there's a known "best way" to initialize and decrement $\epsilon$ (depending on how well-defined this is, it could very naturally lead to a "parameterized" algorithm like you're looking for). $\endgroup$ – Daniel Apon Oct 12 '10 at 15:36
  • $\begingroup$ @Daniel Apon - there is pseudocode for capacity scaling on page 31 of these slides: cs.princeton.edu/~wayne/kleinberg.../07maxflow.pdf $\endgroup$ – dan_x Oct 12 '10 at 15:48
  • $\begingroup$ @Raphael - Note that I'm looking for a single objective that could be e.g. a linear combination of length and fatness. Is that still considered a multicriteria optimization? $\endgroup$ – dan_x Oct 12 '10 at 17:59
  • $\begingroup$ Also, I'm willing to take a "pretty good" path even if it is not optimal. In capacity scaling, for example, we take any path that is at least as fat as $\epsilon$. I'd be happy with some analog that takes into account both shortness and fatness. $\endgroup$ – dan_x Oct 12 '10 at 18:09
2
$\begingroup$

In the spirit of your comment about "pretty good but not necessarily optimal," I present the following idea with absolutely no guarantee of optimality!

For completeness, here is the pseudocode that you referred to (Remark: the algorithm linked assumes edge capacities are integers between 1 and C and that flow and residual capacity values are integral):

Scaling-Max-Flow(G, s, t, C) {
   foreach e ∈ E f(e) ← 0
   Δ ← smallest power of 2 greater than or equal to C
   G_f ← residual graph

   while (Δ ≥ 1) {
      G_f(Δ) ← Δ-residual graph
      while (there exists augmenting path P in G_f(Δ)) {
         f ← augment(f, C, P)
         update G_f(Δ)
      }
      Δ ← Δ / 2
   }
   return f
}

Observe that when $\epsilon$ = 1 ($\epsilon = \Delta$ in the psuedocode), you're just finding paths in shortest to longest order, and when $\epsilon$ is large, you're finding paths in (more or less) fattest to slimmest order. In fact, depending on the instance, the capacity-scaling algorithm finds paths in shortest to longest order within "buckets" of "enough flow."

Then, add another input parameter $0 \le \rho \le 1$ that represents how much you care about "fatness" vs "shortness." In order to ensure we're not massively affecting the runtime, we further require that $\rho$ is a rational number.

Then, each time $\epsilon$ is assigned a value, we additionally take the $\rho$-weighted arithmetic mean (I hope that's the correct term..) between 1 and its current value. That is,

$\epsilon \leftarrow (\rho)\epsilon + (1-\rho)$

For $\rho = 0$, we end up with a pure shortest path algorithm; for $\rho = 1$, we get a pure fattest path algorithm; and for $0 < \rho < 1$ we get something in between. In particular, for some middle value, $\epsilon$ will converge to $\le 1$ more quickly, so you'll get more shortest paths, and fewer fattest paths.

$\endgroup$
  • $\begingroup$ Thanks for the idea -- it's getting close to what I had in mind. My one concern is that this is just a different "decay schedule" for capacity scaling, right? $\endgroup$ – dan_x Oct 12 '10 at 19:53
  • $\begingroup$ As you decay more aggressively, you get shorter paths, and as you decay less aggressively you get fatter paths. What I had in mind was that each path would get a score based on how fat it was and how short it was, then the algorithm would find all paths with score greater than some threshold. $\endgroup$ – dan_x Oct 12 '10 at 19:59
  • $\begingroup$ But if there isn't a standard way of doing this, I can sit down and put some thought into getting an algorithm that does what I want. $\endgroup$ – dan_x Oct 12 '10 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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