Ahuja-Orlin: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
Line 63: Line 63:
Now we know <math>d(u)\leq n</math> for all nodes <math>(u\in V</math>. Next we consider an arbitrary but fixed arc <math>(v,w)\in A</math>. Suppose <math>(v,w)</math> has ben [[Basic flow definitions|saturated]] at least twice during the algorithm. In both iterations, <math>(v,w)</math> is admissible, which means <math>d(v)>d(w)</math>. However, in the meantime, some flow must have been sent back from <math>w</math> to <math>v</math>, which implies <math>d(w)>d(v)</math> in that intermediate iteration. As distance labels are non-decreasing, <math>d(v)</math> must have been increased between any two iterations in which <math>(v,w)</math> is saturated. In summary, each arc is saturated only <math>\mathcal{O}(n)</math> times.
Now we know <math>d(u)\leq n</math> for all nodes <math>(u\in V</math>. Next we consider an arbitrary but fixed arc <math>(v,w)\in A</math>. Suppose <math>(v,w)</math> has ben [[Basic flow definitions|saturated]] at least twice during the algorithm. In both iterations, <math>(v,w)</math> is admissible, which means <math>d(v)>d(w)</math>. However, in the meantime, some flow must have been sent back from <math>w</math> to <math>v</math>, which implies <math>d(w)>d(v)</math> in that intermediate iteration. As distance labels are non-decreasing, <math>d(v)</math> must have been increased between any two iterations in which <math>(v,w)</math> is saturated. In summary, each arc is saturated only <math>\mathcal{O}(n)</math> times.


In each execution of step 2.1, at least one arc is saturated, so the total number of executions of step 2.1 is in <math>\mathcal{O}(nm)</math>. The path contans at most <math>n-1</math> arcs, so the total asymptotic complexity for all executions of step 2.1 isin <math>\mathcal{O}(n^2m</math>.
In each execution of step 2.1, at least one arc is saturated, so the total number of executions of step 2.1 is in <math>\mathcal{O}(nm)</math>. The path contans at most <math>n-1</math> arcs, so the total asymptotic complexity for all executions of step 2.1 isin <math>\mathcal{O}(n^2m)</math>.


== Remark ==
== Remark ==


This algorithm may be seen as a "lazy" variant on [[Edmonds-Karp]]. In fact, the most expensive step there is the computation of a flow-augmenting <math>(s,t)</math>-path. This task amounts to computing the true distance from every node to <math>t</math>. A valid distance labeling may be seen as "lazily evaluated" true distances.
This algorithm may be seen as a "lazy" variant on [[Edmonds-Karp]]. In fact, the most expensive step there is the computation of a flow-augmenting <math>(s,t)</math>-path. This task amounts to computing the true distance from every node to <math>t</math>. A valid distance labeling may be seen as "lazily evaluated" true distances.

Revision as of 12:24, 13 October 2014

General Information

Algorithmic problem: Max-Flow Problems

Type of algorithm: loop

Abstract View

Invariant: After [math]\displaystyle{ i \ge 0 }[/math] iterations:

  1. The flow [math]\displaystyle{ f }[/math] is a fleasible flow.
  2. If all upper bounds are integral, [math]\displaystyle{ f }[/math] is integral as well.
  3. There is a valid distance labeling [math]\displaystyle{ d }[/math] with respect to [math]\displaystyle{ f }[/math].
  4. Each node [math]\displaystyle{ v\in V\setminus\{t\} }[/math] has a current arc, which is either void or one of the outgoing arcs of [math]\displaystyle{ v }[/math].
  5. Stack [math]\displaystyle{ S }[/math] contains a current flow-augmenting path with respect to [math]\displaystyle{ f }[/math]. This path starts with [math]\displaystyle{ s }[/math] and ends at an arbitrary node of [math]\displaystyle{ G }[/math]. Each arc on this path is admissible and the current arc of its tail node.

Variant: Exactly one of the following actions will take place in the current iteration:

  1. An arc is appended to the current path.
  2. At least one arc is saturated.
  3. The distance label of some node is increased.

Break condition: [math]\displaystyle{ d(s)\geq n }[/math], where [math]\displaystyle{ n=|V| }[/math],

Induction basis

Abstract view:

  1. We start with some feasible flow, for example, the zero flow.
  2. For each [math]\displaystyle{ v\in V }[/math], [math]\displaystyle{ d(v) }[/math] is initialized to be the smallest number of arcs from [math]\displaystyle{ v }[/math] to [math]\displaystyle{ t }[/math].
  3. Stack [math]\displaystyle{ S }[/math] is initialized so as to contain [math]\displaystyle{ s }[/math] and no other node.
  4. The current arc of each node [math]\displaystyle{ v\in V }[/math] is reset to be the very first outgoing arc of [math]\displaystyle{ v }[/math].

Implementation:

  1. For all [math]\displaystyle{ a \in A }[/math], set [math]\displaystyle{ f(a):=0. }[/math]
  2. Run a BFS on the transpose of [math]\displaystyle{ G }[/math] with start node [math]\displaystyle{ t }[/math] and unit arc lengths; the resulting distances are the [math]\displaystyle{ d }[/math]-labels.
  3. Create [math]\displaystyle{ S }[/math] and push [math]\displaystyle{ s }[/math] onto [math]\displaystyle{ S }[/math].
  4. Reset the current arcs.

Proof: Obvious.

Induction step

Abstract view:

  1. Let [math]\displaystyle{ v }[/math] be the top element of [math]\displaystyle{ S }[/math], that is, the endnode of the corresponding path.
  2. If [math]\displaystyle{ v=t }[/math]:
    1. Augment the current flow along the path correspoding to [math]\displaystyle{ S }[/math].
    2. Remove all nodes but [math]\displaystyle{ s }[/math] from [math]\displaystyle{ S }[/math].
    3. Otherwise:
      1. While the current arc of [math]\displaystyle{ v }[/math] is not void and not admissible or points [math]\displaystyle{ s }[/math]: Move the current arc one step forward.
      2. If the current arc is void: Set [math]\displaystyle{ d(v):=\tilde{d}+1 }[/math], where [math]\displaystyle{ \tilde{d} }[/math] denotes the minimum value [math]\displaystyle{ d(w) }[/math] over all outgoing arcs [math]\displaystyle{ (v,w) }[/math] of [math]\displaystyle{ v }[/math] in the residual network.
      3. Otherwise, that is, if the current arc is some arc [math]\displaystyle{ (v,w) }[/math]: Push [math]\displaystyle{ w }[/math] on [math]\displaystyle{ S }[/math].

Proof: The variant and points 1, 2, and 4 are obvious. For point 5, note that step 2.3.1 skips all non-admissible arcs, so step 2.3.3 is only applied to admissible arcs. Finally, point 3 of the invariant follows from the maximally conservative increase of [math]\displaystyle{ d(v) }[/math] in step 2.3.2.

Complexity

First we show that no distance label [math]\displaystyle{ d(v) }[/math] may become higher than [math]\displaystyle{ n }[/math] (in particular, the total number of executions of step 2.3.2 over all iterations is in [math]\displaystyle{ \mathcal{O}(n^2) }[/math].

To see that, recall [math]\displaystyle{ d(s)\lt n }[/math] from the break condition. Whenever the distance label [math]\displaystyle{ d(v) }[/math] of a node [math]\displaystyle{ v\in V }[/math] is increased, [math]\displaystyle{ v }[/math] is the endnode of the current path, which consists solely of admissible arcs. Due to the definition of admissible arcs, it is [math]\displaystyle{ d(v)\leq d(s) }[/math] immediately before the current iteration (equality only if [math]\displaystyle{ v=s }[/math]). Let [math]\displaystyle{ (v,w) }[/math] be an arc such that [math]\displaystyle{ \tilde{d}=d(w) }[/math]. For the same reason, it is [math]\displaystyle{ d(w)\lt d(s) }[/math], which implies [math]\displaystyle{ d(v)\leq d(s) }[/math] immediately after the current iteration.

Now we know [math]\displaystyle{ d(u)\leq n }[/math] for all nodes [math]\displaystyle{ (u\in V }[/math]. Next we consider an arbitrary but fixed arc [math]\displaystyle{ (v,w)\in A }[/math]. Suppose [math]\displaystyle{ (v,w) }[/math] has ben saturated at least twice during the algorithm. In both iterations, [math]\displaystyle{ (v,w) }[/math] is admissible, which means [math]\displaystyle{ d(v)\gt d(w) }[/math]. However, in the meantime, some flow must have been sent back from [math]\displaystyle{ w }[/math] to [math]\displaystyle{ v }[/math], which implies [math]\displaystyle{ d(w)\gt d(v) }[/math] in that intermediate iteration. As distance labels are non-decreasing, [math]\displaystyle{ d(v) }[/math] must have been increased between any two iterations in which [math]\displaystyle{ (v,w) }[/math] is saturated. In summary, each arc is saturated only [math]\displaystyle{ \mathcal{O}(n) }[/math] times.

In each execution of step 2.1, at least one arc is saturated, so the total number of executions of step 2.1 is in [math]\displaystyle{ \mathcal{O}(nm) }[/math]. The path contans at most [math]\displaystyle{ n-1 }[/math] arcs, so the total asymptotic complexity for all executions of step 2.1 isin [math]\displaystyle{ \mathcal{O}(n^2m) }[/math].

Remark

This algorithm may be seen as a "lazy" variant on Edmonds-Karp. In fact, the most expensive step there is the computation of a flow-augmenting [math]\displaystyle{ (s,t) }[/math]-path. This task amounts to computing the true distance from every node to [math]\displaystyle{ t }[/math]. A valid distance labeling may be seen as "lazily evaluated" true distances.