Improved max flow path augmenting

a) Find max residual path augment along it

O (m² log U)

b) Find residual path that is "sufficiently" large.

O (m² log U)

Find residual arcs with capacity >  keep a network with

only those arcs.

 Augment on paths

 Update  =  / 2 until  = 1

 In each scaling phase ( value) there is a maximum of O(m) augmentations

[each augmentation O(m)]  hence O(m² log U)

2. Augment along shortest path 7.4

(smallest number of arcs)
O(n²m)
Flavor of shortest path idea in preflow push discussion
Preflow Push Algorithms
The best preflow push algorithms outperform the best path augmenting in theory and in practice.
Push flow along individual arcs, not paths.
But, doing this may violate mass balance constraints.
Definition: Preflow

A preflow is any flow satisfying

1. 
   Flow bound constraints
   

Definition An active node i is one with e(i) > 0.

 s & t are never active by convention

Thus select active nodes, because they are infeasible, and make them feasible.

Closer means to a node with a shorter distance label

Distance labels, d(i), are set for each node i and have these properties

1. d(t) = 0

2. d(i)  d(j) + 1 for every arc (i, j) in the residual network G(x).

Can show Property 7.1

If the distance labels are valid (satisfy 1 & 2 above) then the distance label d(i) is a lower bound on the length of the shortest directed path from node i to node t in the network.

Thus property 7.2 is obvious

If d(s)  n the residual network has no directed path from s to t.

Definition: d(i) is exact if d(i) = the length of the shortest path from i to t in the residual network.

Definition: An arc (i, j) in the residual network is admissible if d(i) = d(j) + 1, else it is inadmissible.

x : = 0;

x_sj : = u_sj for each arc (s, j)  A (s);

d(s) : = n;

end;

procedure push/relabel(i);

begin

if the network contains an admissible arc (i, j) then

push  : = min {e(i), r_ij} units of flow from node i to node j

preprocess;

select an active node i;

push/relabel (i);

end;

end;
Water Analogy
Flexible pipes, joints, d(.)

Arcs nodes how high node is off of the ground

admissible arc -- downhill

Move source up, water flows down.

Preprocessing

1. Pushes initial flows to arcs adjacent to s, gives them e(i) > 0

so the algorithm has a starting point.

2. Arcs in A(s) are saturated,  not admissible. Setting

d(s) = n satisfies d(i)  d(j) + 1 for all (i, j) in the residual network G(x)

3. 
   d(s) = n => residual network has no path from s to t
   

d(i) non decreasing  never get directed path from s to t

4. If algorithm terminates must be opt.

 Excess at s or t
 Since d(s) = n, residual network has no path from s to t.

Termination criteria for path augmenting

1. 
   Can show d(i) are always valid.
   

2. 
   We don't increase the distance labels "too many" times.
   

a. Lemma 7.11 At any stage of the preflow push algorithm, each node i with positive excess is connected to node s by a directed path from node i to s in the residual network.

e(s)  0 e(i)  0 i  N - {s}

Flows in G decompose to

s to t

s to active nodes (e(i) > 0)

cycles

 must have path, P, s to i in G

G(x) has reverse of P, directed i to s

Thus, when we relabel we minimize over a non-empty set.

Last time i relabeled e(i) > 0,  path P

from i to s with maximum n-2 arcs

since d(s) = n & d(k)  d(l) + 1 for all

(k, l)  P => d(i)  d(s) + P<2n

c. Since we increase d(i) by at least 1 each time there is a maximum of 2n increases for node i.

 total increases at most 2n²
3. Can show

4. 
   Maximum nm saturating pushes
   

4. 
   O(n²m) non-saturating pushes
   

4. Keep active nodes on a LIST

5. Can show  that the generic preflow push algorithm is O(n²m)