Finding short and fat paths 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.
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 &lt; \rho &lt; 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.