Improved max flow path augmenting
1. Augment in "large" increments
a) Find max residual path augment along it
O (m^{2} log U)
b) Find residual path that is "sufficiently" large.
Capacity scaling (Section 7.3)
O (m^{2} log U)
Find residual arcs with capacity > keep a network with
only those arcs.
initially =
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^{2} log U)
2. Augment along shortest path 7.4
(smallest number of arcs)
O(n^{2}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

Flow bound constraints
2) for all
Flow entering can exceed flow leaving.
Thus, may violate mass balance constraint.
The idea is to push flow on arcs, violate mass balance, then restore mass balance (feasibility) for nodes.
Push toward the sink to do this, if we can't push toward the sink then push toward the source.
Definition e(i) excess of each node i N
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.
Where to push flow?
Closer to the sink
Closer means to a node with a shorter distance label
Distance Labels
What is a 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.
We only push flow on admissible arcs.
Definition: A path from s to t consisting of all admissible arcs is an admissible path. An admissible path is a shortest augmenting path from
s to t.
Generic Preflow Push Algorithm
procedure preprocess;
begin
x : = 0;
compute the exact distance labels d(i);
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
else replace d(i) by min {d(j) + 1 : (i, j) A(i) and r_{ij} > 0};
end;
Definition  arc saturated if = r_{ij}
algorithm preflowpush;
begin
preprocess;
while the network contains an active node do
begin
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.
Increase d() until flow goes to sink or source
When you are stuck at a node with all uphill flows, increase d() until a downward flow exists
Why does the generic preflow push algorithm work?
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)

d(s) = n => residual network has no path from s to t
d(i) non decreasing never get directed path from s to t
(Prop. 7.2: d(s) n => no directed path s to t in G(x))
no need to push again from s
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
Does the algorithm terminate?
Yes!

Can show d(i) are always valid.

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.
By the flow decomposition theorem, since
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
but flow from s to t, and cycles don't help e(i) > 0
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 nonempty set.
b. Lemma 7.12 i N d(i) < 2n
Last time i relabeled e(i) > 0, path P
from i to s with maximum n2 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^{2}
3. Can show

Maximum nm saturating pushes

O(n^{2}m) nonsaturating pushes
4. Keep active nodes on a LIST
5. Can show that the generic preflow push algorithm is O(n^{2}m)
Share with your friends: 