Subhash Suri UC Santa BarbaraNetwork Flows1. Flows deal with network models whereedges have capacity constraints.2. Shortest paths deal with edge costs.s tu vx y45324216 53. Network flow formulation:• A network G = (V, E).• Capacity c(u, v) ≥ 0 for edge (u, v).• Assume c(u, v) = 0 if (u, v) 6∈ E.• Source s and sink t.Subhash Suri UC Santa BarbaraNetwork Flows1. Flow f : E → R+such that• f(u, v) ≤ c(u, v), for all (u, v) ∈ E.•Pv∈Vf(v, u) =Pv∈Vf(u, v), for u 6= s, t.2. These conditions are called CapacityConstraint and Flow Conservation.3. Value of flow f is |f| =Pv∈Vf(s, v).s tu vx y(1,2)(4,4)(2,6)(0,5)(0,1)(2,2)(3,4)(3,5)(2,3)4. (Max Flow Problem:) Given G, s and t,determine max-valued flow from s to t.5. Optional Lower Bound: For some edges,f(u, v) ≥ l(u, v).Subhash Suri UC Santa BarbaraApplications:Transportation1. Company wants to ship hockey pucksfrom Vancouver (factory) to Winnpeg(warehouse).2. Trucking companies lease space onestablished routes (lanes).3. Lane capacity in number of standardcrates.svxytu11/1411/16Vanc.WinnipegReginaCalg.Edm.Sask.12/121/40/108/134/97/74/415/204. What is the maximum number of unitsthat can be shipped from V to W ?5. In this example, |f| = 19.Subhash Suri UC Santa BarbaraApplications: MatrixRounding1. Given a p × q matrix of reals, row sums αi,and column sums βj.2. We can round any matrix entry a up ordown (i.e., to dae or to bac).3. Round entries as well as row and columnsums so that sums are consistent in therounded matrix.3.19.63.66.87.32.40.71.26.517.212.711.316.310.414.5Col SumRow SumSubhash Suri UC Santa BarbaraApplications: MatrixRounding1. Node i for row i, and node j0for column j.Two additional nodes s and t.2. Edge (i, j0) for each matrix entry Dij. Edge(s, i) for row-sum i; edge (j0, t) for columnsum j.3. Lower and upper bounds for (i, j0)correspond to rounding down androunding up Dij.(17,18)(12,13)(11,12)(3,4)(6,7)(7,8)(2,3)(0,1)(3,4)(1,2)(6,7)(14,15)(10,11)(16,17)st1 1’2 2’33’4. Consisten matrix rounding if and onlyfeasible flow in the network.Subhash Suri UC Santa BarbaraApplications: Scheduling1. Set of jobs, J, to be scheduled on Midentical processors.2. Each job has 3 time parameters: pi(processing time), ri(ready forscheduling), di(due date).3. Clearly, di≥ ri+ pimust hold.4. Preemption allowed: jobs can beinterrupted, and restarted later on adifferent machine.5. Example.Job (j)Process Time piRelease Time riDue Date di11.52431.253.62.1313 554796. M = 3 machines.Subhash Suri UC Santa BarbaraApplications: Scheduling1. Break the time line into at most 2J − 1disjoint intervals. No job begins or endsinside an interval, so the set of jobsavailable within an interval is constant.T13T34T45T57T79T13T34T45T57T79s1234123 4567 89t1.2536111221.52.13.621126362134Subhash Suri UC Santa BarbaraApplications: Scheduling1. Source node s, sink node t, node for eachjob, and node for each interval.2. Connect s to job j with capacity pi.3. Connect each interval node Tjkto sink twith capacity (k − j)M, indicating thenumber of machine units available in thatinterval.4. Connect a job i to each interval Tjksuchthat ri≤ j and di≥ k. The capacity of thisedge is (k − j) indicating the number ofmachine units allotable to job i in thisinterval.5. The scheduling problem has a solution ifand only if there is max flow of valuePjpj.Subhash Suri UC Santa BarbaraFord-Fulkerson Method1. Developed by Ford and Fulkerson [1956]2. Widely used, and influential ideas:Augmentation, residual network, andfamous Min-Cut Max-Flow theorem.Generic FF (G, s, t)• Initialize f = 0;• while there is an augmenting path paugmentfalongp3. Basically, a greedy method, but...21211111FlowCapacitySubhash Suri UC Santa BarbaraResidual Networks1. Previous example shows augmenting on Gmay not find optimal flow.2. Given current flow f, define residualcapacity of an edge (u, v) as follows:cf(u, v) = c(u, v) − f(u, v).3. Residual capacity is the additional flowone can send on an edge, possibly bycanceling some flow in opposite edge.u v011/164. cf(u, v) = 16 − 11 = 5.5. cf(v, u) = 0 − 11 = 11.Subhash Suri UC Santa BarbaraResidual Networks1. Residual network Gfis (V, Ef), whereEf= {(u, v) | cf(u, v) > 0}.2. Note that |Ef| ≤ 2|E|.5/53/42/20/12/3uuyvxyvx12521Residual NetworkFlow f133. When is an edge (u, v) ∈ Ef?• if (u, v) ∈ E and f(u, v) < c(u, v), or• if (v, u) ∈ E and f(v, u) > 0.Subhash Suri UC Santa BarbaraAugmentation1. An augmenting path p is a simple path inGffrom s to t.2. Residual capacity of p:cf(p) = min{cf(u, v) | (u, v) ∈ p}.3. By definition, cf(p) > 0.1/11/21/11/20/10/11/11/11111111111Flow fResidual Network4. Can you spot an augmenting path?5. How to prove no more flow possible?Subhash Suri UC Santa BarbaraCuts1. A cut (S, T ) is a partition of V with s ∈ Sand t ∈ T .2. f(S, T ) is the net flow across cut (S, T ).3. c(S, T ) is the max capacity of cut (S, T );use only forward edges.sv wtxy4/911/168/131/4 0/1011/1412/127/74/415/20A cut4. In this example, f(S, T ) = 12 − 4 + 11 = 19.5. c(S, T ) = 12 + 14 = 26.Subhash Suri UC Santa BarbaraFlows and Cuts• No matter how you separate s and t, thenet flow across (S, T ) is exactly |f|.Cut Lemma: If f is a flow and (S, T ) a cut inG, then f(S, T ) = |f|.Proof:f(S, T ) =Xv∈S,w∈Tf(v, w)=Xv∈S,w∈Vf(v, w) −Xv∈S,w∈Sf(v, w)=Xv∈S,w∈Vf(v, w)= |f|• UsePv∈S,w∈Sf(v, w) = 0 since each (u, v) iscounted twice canceling itself out.Subhash Suri UC Santa BarbaraMaxflow-Mincut TheoremTheorem: The following are equivalent:1. f is a maxflow.2. No augmenting path in Gf.3. |f| = c(S, T ) for some cut (S, T ).Proof:• (1) ⇒ (2). Aug. path increases f.• (2) ⇒ (3). Define reachable setS = {v | ∃ path from s to v in Gf}T = V − S. Then, t ∈ T —because noaugmenting path. For any u ∈ S, v ∈ T ,f(u, v) = c(u, v); otherwise, (u, v) ∈ Ef, and vwill be reachable from s. Thus,|f| = f(S, T ) = c(S, T ).• (3) ⇒ (1). By Cut Lemma,|f| = f(S, T ) ≤ c(S, T ). So, equality meansflow is a maxflow.Subhash Suri UC Santa BarbaraFord Fulkerson Algorithm1. for each edge (u, v) ∈ E do2. f(u, v) = f(v, u) = 0;3. while there is a path p in Gfdo4. cf(p) = min{cf(u, v) | (u, v) ∈ p}5. for each (u, v) ∈ p do6. f(u, v) = f(u, v) + cf(p)7. f(v, u) = −f(u, v)8. end9. end.Subhash Suri UC Santa BarbaraExample of FFSubhash Suri UC Santa BarbaraAnalysis of Ford-Fulkerson• Correctness follows from Mincut Maxflowtheorem.• BFS to find augmenting path takes