15.082J and 6.855J and ESD.78J October 21, 2010Max Flows 42Overview of today’s lecture Scaling Algorithms Potential function analysis The Excess Scaling Algorithm O(n2log U) non-saturating pushes, where U = 1 + max{uij: (i, j) ∈ A}  O(nm + n2 log U) running time. A proof that Highest Level Preflow Push uses O(n2m1/2) non-saturating pushes.Scaling Algorithms3Generic Scaling AlgorithmΔ := 2Kfor some selected value Kdetermine a Δ-optimal solution xwhile Δ > 1 doy := ImproveApprox(x, Δ)x := yΔ := Δ/2 1. Define a concept called Δ-optimal, where Δ is some positive integer, and where a 1-optimal solution is optimal for the original problem.2. Develop a subroutine that efficiently determines Δ0-optimum solution where Δ0is some (possibly large) power of 23. Develop a subroutine Improve-Approx that transforms a Δ-optimal solution into a Δ/2-optimal solution.4The Capacity Scaling Algorithm A flow x is called Δ-maximum if there is no augmenting path in G(x) of capacity  or more. Note. If Δ ≥ U, then x = 0 is Δ-maximum. U = 1 + max {uij: (i, j) ∈ A}  Subroutine ImproveApprox(x,Δ): takes a flow that is -maximum and outputs a flow that is /2-maximum. We refer to a path in G(x) as a Δ-augmenting if it is an s-t path whose capacity is at least Δ.ImproveApprox(x,Δ)while there is a Δ/2-augmenting path in G(x) dofind a Δ/2-augmenting path P in G(x);augment flow along P;update residual capacities and data structures;5Analysis of Capacity Scaling1234 5678103052554102015569stLemma. At the beginning of the Δ-scaling phase, there is a an s-t cut (S, T) such that the capacity of each arc (i, j) from S to T is less than Δ. S = { j : there is a path P of capacity ≥ Δ from s to j}The residual capacity of (S, T) is less than mΔ. Δ = 106Analysis of Capacity ScalingCorollary. The number of augmentations per scaling phase is at most 2m.Proof. Each augmentation reduces the residual capacity of the cut by at least Δ/2.Lemma. The number of times that ImproveApprox is called is at most ⎡log U⎤Proof. Initially Δ = 2K, where K = ⎡log U⎤At each subsequent iteration Δ is halved.The algorithm stops when Δ = 1.The running time per scaling phase is O(m2).The total running time is O(m2log U)The running time can be improved to O(nm log U)A previewNext: an algorithm that is based on scaling excesses rather than capacities.Based on preflow-pushAt the Δ-scaling phases, all excesses are less than Δ.78A Review of PreflowsAt each intermediate stages we permit more flow arriving at nodes than leaving (except for s)A preflow is a function x: A → R s.t. 0 ≤ x ≤ u and such that e(i) = ∑j∈Nxji- ∑j∈Nxij≥ 0, for all i ∈ N – {s, t}.i.e., e(i) = excess at i = net excess flow into node i.The excess is required to be nonnegative.9A Feasible PreflowThe excess e(j) at each node j ≠ s, t is the flow in minus the flow out.s342 5t333222212100Note: total excess = flow out of s minus flow into t.10Distance LabelsDistance labels d( ) are valid for G(x) ifi. d(t) = 0ii. d(i) ≤ d(j) + 1 for each (i,j) ∈ G(x)Defn. An arc (i, j) is admissible if rij> 0 and d(i) = d(j) + 1. Lemma. Let d( ) be a valid distance label. Then d(i) is a lower bound on the distance from i to t in the residual network.i tP = the shortest path from i to t in G(x)d( )01234 2311Distance labels and gapsWe say that there is a gap at a distance level k (0 < k < n) if there is no node with distance label k.Lemma. Suppose there is a gap at distance level k. Then for any node j with d(j) > k, there is no path from j to t in the residual network.Proof. The shortest path from j to t would have to pass through a node whose distance level is k.i tP = the shortest path from i to t in G(x)d( )01234 2312Active nodes in the residual networkA node j in G\{s} is active if:• e(j) > 0 and • there is no gap at a distance level less than d(j)The preflow push algorithm will push flow from active nodes “towards the sink”, relying on d( ).6312 10210427stkd( ) = kw e( ) = w13Goldberg-Tarjan Preflow Push AlgorithmProcedure Preprocessx :=0;compute the exact distance labels d(i) for each node;xsj:= usjfor each arc (s, j) ∈ A(s); d(s) := n;Algorithm PREFLOW-PUSH;preprocess;while there is an active node i do select an active node i;push/relabel(i);convert the max preflow into a max flowNote: the “while loop” ends when there are no active nodes; i.e., if e(j) > 0, then d(j) is above a gap.14The Excess Scaling Algorithm A preflow x is called Δ-maximum if e(j) < Δ for all j ≠ s, t. Note. If Δ ≥ U, then the preflow after the preprocess step is Δ-maximum. If a preflow is 1-maximum and if d(s) = n, then the preflow is a maximum flow. Subroutine ImproveApprox(x,Δ): takes a preflow x that is -maximum and outputs a preflow that is /2-maximum.Excess Scaling AlgorithmΔ := 2Kwhere K = ⎡ log U ⎤Preprocesswhile Δ > 1 doy := ImproveApprox(x, Δ)x := yΔ := Δ/2convert the maximum preflow x into a maximum flow15Improve ApproxWe say that a node is Δ-active if1. e(i) ≥ Δ2. node i is not above a gap If a node i is above a gap, then there is no path from i to t in G(x). Subroutine ImproveApprox(x,Δ)while the G(x) has a Δ/2-active node j doamong Δ/2-active nodes, choose i with minimum distance labelperform push/relabel(i) where the amount pushed in (i, j) is min (Δ/2, rij)475620 302 40Δ = 64Send 2 units of flow in (7, 4). Then send 32 units of flow in (7, 5)16Lemmas about pushingLemma 1. Throughout ImproveApprox, e(j) < Δ for all active nodes j.Proof. If we push in (i, j), then e(j) < Δ/2 before the push, and the amount pushed is at most Δ/2. 475620 302 40Δ = 64Send 2 units of flow in (7, 4). Then send 32 units of flow in (7, 5) Lemma 2. Each non-saturating push sends exactly Δ/2 units of flow.Proof. The amount pushed in (i, j) is min (Δ/2, rij).Analysis of the Excess Scaling AlgorithmTheorem. The Excess Scaling Algorithm finds a maximum flow in O(nm + n2log U) steps.Proof. We have already shown the following in the analysis of preflow-push algorithms.1. If it terminates, it terminates with a max flow2. The time spent in all steps other than nonsaturating pushes is O(nm).3. What remains to be proved: • A Δ/2-active node with lowest distance label can be selected in O(1) steps. • The number of nonsaturating pushes is O(n2log U). For this we will rely on a new potential function.1718Selecting Δ-active