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

<p>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):</p>

<pre>
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
}
</pre>

<p>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."</p>

<p>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.</p>

<p>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,</p>

<p>$\epsilon \leftarrow (\rho)\epsilon + (1-\rho)$</p>

<p>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.</p>

CC BY-SA 2.5
2010-10-12T19:53:26.583Z
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?
dan_x
CC BY-SA 2.5
2010-10-12T19:59:20.017Z
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.
dan_x
CC BY-SA 2.5
2010-10-12T20:00:59.883Z
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.
dan_x
CC BY-SA 2.5
2010-10-12T19:12:48.803Z
2010-10-12T19:18:40.447Z
2010-10-12T19:18:40.447Z
Daniel Apon
<p><strong>Motivation:</strong> 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 <em>shortest</em> paths.</p>

<p>Empirically, it has been observed that we might also want to find <em>fat</em> (is there a better term for this?) paths.  For example, when using <em>capacity scaling</em>, 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.</p>

<p>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.)</p>

<blockquote>
  <p><strong>Question:</strong> 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.</p>
</blockquote>

CC BY-SA 2.5
2010-10-12T09:18:07.763Z
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.
Raphael
CC BY-SA 2.5
2010-10-12T15:36:31.363Z
@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).
Daniel Apon
CC BY-SA 2.5
2010-10-12T15:48:35.417Z
@Daniel Apon - there is pseudocode for capacity scaling on page 31 of these slides: http://www.cs.princeton.edu/~wayne/kleinberg.../07maxflow.pdf
dan_x
CC BY-SA 2.5
2010-10-12T17:59:06.447Z
@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?
dan_x
CC BY-SA 2.5
2010-10-12T18:09:14.823Z
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.
dan_x
CC BY-SA 2.5
2010-10-13T07:35:35.050Z
dan, if you have a weighted sum (or similar) of some criteria you are left with the basic shortest path problem. Just combine the criteria to a single one and use common algorithms.
Raphael
<ds.algorithms><graph-theory><graph-algorithms>
Finding short and fat paths
dan_x
# Finding short and fat paths

(Asked by: username_0 on 2010-10-12)

**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.

**Tags:** ds.algorithms, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: 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.  
> **username_2**: @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).  
> **username_0**: @username_2 - there is pseudocode for capacity scaling on page 31 of these slides: http://www.cs.princeton.edu/~wayne/kleinberg.../07maxflow.pdf  
> **username_0**: @username_1 - 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?  
> **username_0**: 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.  
> **username_1**: dan, if you have a weighted sum (or similar) of some criteria you are left with the basic shortest path problem. Just combine the criteria to a single one and use common algorithms.  

---

## 1 answers

### Answer by username_2 on 2010-10-12. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_0**: 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.  
> **username_0**: 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.  

---

