Question? Leave a message!




maxflow-mincut theorem

maxflow-mincut theorem
ROBERT SEDGEWICK KEVIN WAYNE Algorithms 6.4 MAXIMUM FLOW introduction ‣ FordFulkerson algorithm ‣ maxflowmincut theorem ‣ Algorithms FOUR TH EDITION analysis of running time ‣ Java implementation ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu applications ‣6.4 MAXIMUM FLOW introduction ‣ FordFulkerson algorithm ‣ maxflowmincut theorem ‣ Algorithms analysis of running time ‣ Java implementation ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu applications ‣Mincut problem Input. An edgeweighted digraph, source vertex s, and target vertex t. each edge has a positive capacity capacity 9 15 10 4 15 10 s 8 10 t 5 15 6 10 4 15 16 3Mincut problem Def. A stcut (cut) is a partition of the vertices into two disjoint sets, with s in one set A and t in the other set B. Def. Its capacity is the sum of the capacities of the edges from A to B. 10 s t 5 15 capacity = 10 + 5 + 15 = 30 4Mincut problem Def. A stcut (cut) is a partition of the vertices into two disjoint sets, with s in one set A and t in the other set B. Def. Its capacity is the sum of the capacities of the edges from A to B. 10 s t 8 don't count edges from B to A 16 capacity = 10 + 8 + 16 = 34 5Mincut problem Def. A stcut (cut) is a partition of the vertices into two disjoint sets, with s in one set A and t in the other set B. Def. Its capacity is the sum of the capacities of the edges from A to B. Minimum stcut (mincut) problem. Find a cut of minimum capacity. 10 s t 8 10 capacity = 10 + 8 + 10 = 28 6Mincut application (RAND 1950s) "Free world" goal. Cut supplies (if cold war turns into real war). rail network connecting Soviet Union with Eastern European countries (map declassified by Pentagon in 1999) Figure 2 7 From Harris and Ross 1955: Schematic diagram of the railway network of the Western So vietUnionandEasternEuropeancountries, withamaximumflowofvalue163,000tonsfrom Russia to Eastern Europe, and a cut of capacity 163,000 tons indicated as ‘The bottleneck’.Potential mincut application (2010s) Governmentinpower’s goal. Cut off communication to set of people. 815 10 6 15 Maxflow problem Input. An edgeweighted digraph, source vertex s, and target vertex t. each edge has a positive capacity capacity 9 15 4 s t 5 8 10 15 4 16 9 10 1010 / 15 5 / 10 0 / 6 5 / 15 Maxflow problem Def. An stflow (flow) is an assignment of values to the edges such that: Capacity constraint: 0 ≤ edge's flow ≤ edge's capacity. Local equilibrium: inflow = outflow at every vertex (except s and t). capacity flow inflow at v = 5 + 5 + 0 = 10 5 / 9 outflow at v = 10 + 0 = 10 0 / 15 0 / 4 s t 5 / 5 5 / 8 10 / 10 0 / 15 0 / 4 10 / 16 10 10 / 10 10 / 10 v10 / 15 5 / 10 0 / 6 5 / 15 Maxflow problem Def. An stflow (flow) is an assignment of values to the edges such that: Capacity constraint: 0 ≤ edge's flow ≤ edge's capacity. Local equilibrium: inflow = outflow at every vertex (except s and t). Def. The value of a flow is the inflow at t. we assume no edges point to s or from t 5 / 9 0 / 15 0 / 4 s t value = 5 + 10 + 10 = 25 5 / 5 5 / 8 10 / 10 0 / 15 0 / 4 10 / 16 11 10 / 10 10 / 1013 / 15 8 / 10 3 / 6 2 / 15 Maxflow problem Def. An stflow (flow) is an assignment of values to the edges such that: Capacity constraint: 0 ≤ edge's flow ≤ edge's capacity. Local equilibrium: inflow = outflow at every vertex (except s and t). Def. The value of a flow is the inflow at t. Maximum stflow (maxflow) problem. Find a flow of maximum value. 8 / 9 0 / 15 0 / 4 s t value = 8 + 10 + 10 = 28 5 / 5 8 / 8 10 / 10 0 / 15 0 / 4 13 / 16 12 10 / 10 10 / 10Maxflow application (Tolstoǐ 1930s) Soviet Union goal. Maximize flow of supplies to Eastern Europe. flow capacity rail network connecting Soviet Union with Eastern European countries (map declassified by Pentagon in 1999) Figure 2 13 From Harris and Ross 1955: Schematic diagram of the railway network of the Western So vietUnionandEasternEuropeancountries, withamaximumflowofvalue163,000tonsfrom Russia to Eastern Europe, and a cut of capacity 163,000 tons indicated as ‘The bottleneck’.Potential maxflow application (2010s) "Free world" goal. Maximize flow of information to specified set of people. facebook graph 1413 / 15 8 / 10 3 / 6 2 / 15 Summary Input. A weighted digraph, source vertex s, and target vertex t. Mincut problem. Find a cut of minimum capacity. Maxflow problem. Find a flow of maximum value. 8 / 9 0 / 4 0 / 15 10 s 8 / 8 t s t 5 / 5 10 / 10 8 0 / 4 0 / 15 10 13 / 16 value of flow = 28 capacity of cut = 28 Remarkable fact. These two problems are dual 15 10 / 10 10 / 106.4 MAXIMUM FLOW introduction ‣ FordFulkerson algorithm ‣ maxflowmincut theorem ‣ Algorithms analysis of running time ‣ Java implementation ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu applications ‣0 / 15 0 / 10 0 / 6 0 / 15 FordFulkerson algorithm Initialization. Start with 0 flow. flow capacity initialization 0 / 9 0 / 4 0 / 15 value of flow s 0 0 / 5 0 / 10 t 0 / 8 0 / 4 0 / 15 0 / 16 17 0 / 10 0 / 100 / 15 0 / 10 0 / 6 10 — 0 / 15 0 / 15 Idea: increase flow along augmenting paths Augmenting path. Find an undirected path from s to t such that: Can increase flow on forward edges (not full). Can decrease flow on backward edge (not empty). st 1 augmenting path bottleneck capacity = 10 0 / 9 0 / 4 0 / 15 10 s 0 + 10 = 10 0 / 5 — 0 / 10 0 / 10 t 0 / 8 0 / 4 0 / 15 0 / 16 18 10 — 0 / 10 0 / 10 0 / 1010 0 / 15 0 / 15 — 0 / 10 0 / 6 10 / 15 Idea: increase flow along augmenting paths Augmenting path. Find an undirected path from s to t such that: Can increase flow on forward edges (not full). Can decrease flow on backward edge (not empty). nd 2 augmenting path 0 / 9 0 / 4 0 / 15 s 10 + 10 = 20 0 / 5 10 / 10 t 0 / 8 0 / 4 0 / 15 10 — 0 / 16 0 / 16 19 10 / 10 10 — 0 / 10 0 / 1010 / 15 5 — 0 / 10 0 / 10 0 / 6 5 10 / 15 10 / 15 — Idea: increase flow along augmenting paths Augmenting path. Find an undirected path from s to t such that: Can increase flow on forward edges (not full). Can decrease flow on backward edge (not empty). rd 3 augmenting path backward edge 5 (not empty) — 0 / 9 0 / 9 0 / 4 0 / 15 5 5 s 20 + 5 = 25 — 0 / 5 0 / 5 — 10 / 10 t 0 / 8 0 / 8 0 / 4 0 / 15 10 / 16 20 10 / 10 10 / 1013 10 / 15 10 / 15 — 8 — 5 / 10 5 / 10 3 0 / 6 — 0 / 6 2 5 / 15 5 / 15 — Idea: increase flow along augmenting paths Augmenting path. Find an undirected path from s to t such that: Can increase flow on forward edges (not full). Can decrease flow on backward edge (not empty). th 4 augmenting path backward edge 8 (not empty) — 5 / 9 5 / 9 0 / 4 0 / 15 8 s 25 + 3 = 28 5 / 5 10 / 10 t — 5 / 8 5 / 8 0 / 4 0 / 15 13 10 / 16 10 / 16 — 21 10 / 10 10 / 1013 / 15 8 / 10 3 / 6 2 / 15 Idea: increase flow along augmenting paths Termination. All paths from s to t are blocked by either a Full forward edge. Empty backward edge. no more augmenting paths 8 / 9 0 / 4 0 / 15 s 28 5 / 5 10 / 10 t 8 / 8 0 / 4 0 / 15 full forward edge 13 / 16 empty backward edge 22 10 / 10 10 / 10FordFulkerson algorithm FordFulkerson algorithm Start with 0 flow. While there exists an augmenting path: find an augmenting path compute bottleneck capacity increase flow on that path by bottleneck capacity Questions. How to compute a mincut How to find an augmenting path If FF terminates, does it always compute a maxflow Does FF always terminate If so, after how many augmentations 236.4 MAXIMUM FLOW introduction ‣ FordFulkerson algorithm ‣ maxflowmincut theorem ‣ Algorithms analysis of running time ‣ Java implementation ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu applications ‣10 / 15 5 / 10 0 / 6 5 / 15 Relationship between flows and cuts Def. The net flow across a cut (A, B) is the sum of the flows on its edges from A to B minus the sum of the flows on its edges from B to A. net flow across cut = 5 + 10 + 10 = 25 5 / 9 0 / 15 0 / 4 s t value of flow = 25 5 / 5 5 / 8 10 / 10 0 / 15 0 / 4 10 / 16 25 10 / 10 10 / 1010 / 15 5 / 10 0 / 6 5 / 15 Relationship between flows and cuts Def. The net flow across a cut (A, B) is the sum of the flows on its edges from A to B minus the sum of the flows on its edges from B to A. net flow across cut = 10 + 5 + 10 = 25 5 / 9 0 / 15 0 / 4 s t value of flow = 25 5 / 5 5 / 8 10 / 10 0 / 15 0 / 4 10 / 16 26 10 / 10 10 / 1010 / 15 5 / 10 0 / 6 5 / 15 Relationship between flows and cuts Def. The net flow across a cut (A, B) is the sum of the flows on its edges from A to B minus the sum of the flows on its edges from B to A. net flow across cut = (10 + 10 + 5 + 10 + 0 + 0) – (5 + 5 + 0 + 0) = 25 5 / 9 edges from B to A 0 / 15 0 / 4 s t value of flow = 25 5 / 5 5 / 8 10 / 10 0 / 15 0 / 4 10 / 16 27 10 / 10 10 / 10Relationship between flows and cuts Flowvalue lemma. Let f be any flow and let (A, B) be any cut. Then, the net flow across (A, B) equals the value of f. Intuition. Conservation of flow. Pf. By induction on the size of B. Base case: B = t . Induction step: remains true by local equilibrium when moving any vertex from A to B. Corollary. Outflow from s = inflow to t = value of flow. 2812 / 15 8 / 10 2 / 6 2 / 15 Relationship between flows and cuts Weak duality. Let f be any flow and let (A, B) be any cut. Then, the value of the flow ≤ the capacity of the cut. Pf. Value of flow f = net flow across cut (A, B) ≤ capacity of cut (A, B). flow bounded by capacity flowvalue lemma 8 / 9 0 / 4 0 / 15 10 s 7 / 8 9 / 10 t s t 5 / 5 5 0 / 4 0 / 15 15 12 / 16 value of flow = 27 capacity of cut = 30 29 10 / 10 10 / 10Maxflowmincut theorem Augmenting path theorem. A flow f is a maxflow iff no augmenting paths. Maxflowmincut theorem. Value of the maxflow = capacity of mincut. Pf. The following three conditions are equivalent for any flow f : i. There exists a cut whose capacity equals the value of the flow f. ii. f is a maxflow. iii. There is no augmenting path with respect to f. i ii Suppose that (A, B) is a cut with capacity equal to the value of f. Then, the value of any flow f ' ≤ capacity of (A, B) = value of f. Thus, f is a maxflow. by assumption weak duality 30Maxflowmincut theorem Augmenting path theorem. A flow f is a maxflow iff no augmenting paths. Maxflowmincut theorem. Value of the maxflow = capacity of mincut. Pf. The following three conditions are equivalent for any flow f : i. There exists a cut whose capacity equals the value of the flow f. ii. f is a maxflow. iii. There is no augmenting path with respect to f. ii iii We prove contrapositive: iii ii. Suppose that there is an augmenting path with respect to f. Can improve flow f by sending flow along this path. Thus, f is not a maxflow. 31Maxflowmincut theorem Augmenting path theorem. A flow f is a maxflow iff no augmenting paths. Maxflowmincut theorem. Value of the maxflow = capacity of mincut. Pf. The following three conditions are equivalent for any flow f : i. There exists a cut whose capacity equals the value of the flow f. ii. f is a maxflow. iii. There is no augmenting path with respect to f. iii i Suppose that there is no augmenting path with respect to f. Let (A, B) be a cut where A is the set of vertices connected to s by an undirected path with no full forward or empty backward edges. By definition of cut, s is in A. Since no augmenting path, t is in B. forward edges full; backward edges empty Capacity of cut = net flow across cut = value of flow f. flowvalue lemma 3213 / 15 13 / 15 8 / 10 6 / 6 6 / 6 2 / 15 Computing a mincut from a maxflow To compute mincut (A, B) from maxflow f : By augmenting path theorem, no augmenting paths with respect to f. Compute A = set of vertices connected to s by an undirected path with no full forward or empty backward edges. 8 / 9 0 / 15 0 / 4 s s t 8 / 8 5 / 5 10 / 10 A 3 / 4 3 / 4 0 / 15 full forward edge 16 / 16 forward edge empty backward edge (not full) backward edge (not empty) 33 10 / 10 10 / 106.4 MAXIMUM FLOW introduction ‣ FordFulkerson algorithm ‣ maxflowmincut theorem ‣ Algorithms analysis of running time ‣ Java implementation ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu applications ‣FordFulkerson algorithm FordFulkerson algorithm Start with 0 flow. While there exists an augmenting path: find an augmenting path compute bottleneck capacity increase flow on that path by bottleneck capacity Questions. How to compute a mincut Easy. ✔ How to find an augmenting path BFS works well. If FF terminates, does it always compute a maxflow Yes. ✔ Does FF always terminate If so, after how many augmentations requires clever analysis yes, provided edge capacities are integers (or augmenting paths are chosen carefully) 35FordFulkerson algorithm with integer capacities Important special case. Edge capacities are integers between 1 and U. flow on each edge is an integer Invariant. The flow is integervalued throughout FordFulkerson. Pf. by induction Bottleneck capacity is an integer. Flow on an edge increases/decreases by bottleneck capacity. Proposition. Number of augmentations ≤ the value of the maxflow. Pf. Each augmentation increases the value by at least 1. critical for some applications (stay tuned) Integrality theorem. There exists an integervalued maxflow. Pf. FordFulkerson terminates and maxflow that it finds is integervalued. 360 0 100 0 100 Bad case for FordFulkerson Bad news. Even when edge capacities are integers, number of augmenting paths could be equal to the value of the maxflow. initialize with 0 flow s flow capacity 0 1 t 37 100 100 00 100 0 100 Bad case for FordFulkerson Bad news. Even when edge capacities are integers, number of augmenting paths could be equal to the value of the maxflow. st 1 iteration s 0 1 1 t 38 0 1 100 0 1 1001 100 1 0 100 Bad case for FordFulkerson Bad news. Even when edge capacities are integers, number of augmenting paths could be equal to the value of the maxflow. nd 2 iteration s 1 0 1 t 39 1 100 1 100 01 100 1 100 Bad case for FordFulkerson Bad news. Even when edge capacities are integers, number of augmenting paths could be equal to the value of the maxflow. rd 3 iteration s 0 1 1 t 40 1 2 100 1 2 1002 1 100 2 1 100 Bad case for FordFulkerson Bad news. Even when edge capacities are integers, number of augmenting paths could be equal to the value of the maxflow. th 4 iteration s 1 0 1 t 41 2 100 2 100Bad case for FordFulkerson Bad news. Even when edge capacities are integers, number of augmenting paths could be equal to the value of the maxflow. . . . 4299 100 99 100 Bad case for FordFulkerson Bad news. Even when edge capacities are integers, number of augmenting paths could be equal to the value of the maxflow. th 199 iteration s 0 1 1 t 43 100 99 100 99 100 100100 99 100 100 99 100 Bad case for FordFulkerson Bad news. Even when edge capacities are integers, number of augmenting paths could be equal to the value of the maxflow. th 200 iteration s 1 0 1 t 44 100 100 100 100100 100 100 100 Bad case for FordFulkerson Bad news. Even when edge capacities are integers, number of augmenting paths could be equal to the value of the maxflow. can be exponential in input size Good news. This case is easily avoided. use shortest/fattest path s 0 1 t 45 100 100 100 100How to choose augmenting paths Use care when selecting augmenting paths. Some choices lead to exponential algorithms. Clever choices lead to polynomial algorithms. augmenting path number of paths implementation randomized queue random path ≤ E U stack (DFS) DFS path ≤ E U queue (BFS) shortest path ≤ ½ E V priority queue fattest path ≤ E ln(E U) digraph with V vertices, E edges, and integer capacities between 1 and U 46How to choose augmenting paths Choose augmenting paths with: Shortest path: fewest number of edges. Fattest path: max bottleneck capacity. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems JACK EDMONDS University of Waterloo, Waterloo, Ontario, Canada AND RICHARD M. KARP University of California, Berkeley, California ABSTRACT. This paper presents new algorithms for the maximum flow problem, the Hitchcock transportation problem, and the general minimumcost flow problem. Upper bounds on the numbers of steps in these algorithms are derived, and are shown to compale favorably with upper bounds on the numbers of steps required by earlier algorithms. First, the paper states the maximum flow problem, gives the FordFulkerson labeling method for its solution, and points out that an improper choice of flow augmenting paths can lead to severe computational difficulties. Then rules of choice that avoid these difficulties are given. EdmondsKarp 1972 (USA) Dinic 1970 (Soviet Union) We show that, if each flow augmentation is made along an augmenting path having a minimum number of arcs, then a maximum flow in an nnode network will be obtained after no more than (n a n) augmentations; and then we show that if each flow change is chosen to produce a maximum increase in the flow value then, provided the capacities are integral, a maximum flow will be determined within at most 1 + logM/(M1) if(t, S) augmentations, wheref(t, s) is the value of the maximum flow and M is the maximum number of arcs across a cut. 47 Next a new algorithm is given for the minimumcost flow problem, in which all shortestpath computations are performed on networks with all weights nonnegative. In particular, this algorithm solves the n X n assigmnent problem in O(n 3) steps. Following that we explore a "scaling" technique for solving a minimumcost flow problem by treating a sequence of derived problems with "scaled down" capacities. It is shown that, using this technique, the solution of a Iiitchcock transportation problem with m sources and n sinks, m n, and maximum flow B, requires at most (n + 2) log2 (B/n) flow augmentations. Similar results are also given for the general minimumcost flow problem. An abstract stating the main results of the present paper was presented at the Calgary International Conference on Combinatorial Structures and Their Applications, June 1969. In a paper by l)inic (1970) a result closely related to the main result of Section 1.2 is obtained. Dinic shows that, in a network with n nodes and p arcs, a maximum flow can be computed in 0 (n2p) primitive operations by an algorithm which augments along shortest augmenting paths. KEY WOl¢l)S AND PHPASES: network flows, transportation problem, analysis of algorithms CR CATEGOI.IES: 5.3, 5.4, 8.3 Copyright © 1972, Association for Computing Machinery, Inc. General permission to republish, but not for profit, all or part of this material is granted, provided that reference is made to this publication, to its date of issue, and to the fact that reprinting privileges were granted by permission of the Association for Computing Machinery. Authors' addresses : J. Edmonds, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada; R. M. Karp, College of Engineering, Operations Research Center, University of California, Berkeley, CA 94720; the latter author's research has been partially supported by the National Science Foundation raider Grant GP15473 with the University of California. Jcurnal of the Association for Computing Machinery, Vol. 19, No. 2, Apri 1972. pp. 248264. 6.4 MAXIMUM FLOW introduction ‣ FordFulkerson algorithm ‣ maxflowmincut theorem ‣ Algorithms analysis of running time ‣ Java implementation ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu applications ‣Flow network representation Flow edge data type. Associate flow f and capacity c with edge e = v→w. e e flow f capacity c e e 7 / 9 Flow network data type. Must be able to process edge e = v→w in either direction: include e in adjacency lists of both v and w. Residual (spare) capacity. Forward edge: residual capacity = c – f . e e Backward edge: residual capacity = f . e residual capacity forward edge Augment flow. 2 Forward edge: add ∆ . Backward edge: subtract ∆ . 7 backward edge 49 v w v w9 / 10 9 1 4 / 4 4 Flow network representation includes all edges with Residual network. A useful view of a flow network. positive residual capacity 9 / 9 original network 0 / 15 4 / 4 s t 4 / 10 0 / 8 4 / 5 backward edge (not empty) 9 residual network 15 4 s t 1 6 8 4 4 forward edge (not full) Key point. Augmenting paths in original network are in 11 correspondence with directed paths in residual network. 50 9 / 10 9 1Flow edge API public class FlowEdge public class FlowEdge public class FlowEdge FlowEdge(int v, int w, double capacity) create a flow edge v→w int from() vertex this edge points from int to() vertex this edge points to int other(int v) other endpoint double capacity() capacity of this edge double flow() flow in this edge double residualCapacityTo(int v) residual capacity toward v void addResidualFlowTo(int v, double delta) add delta flow toward v residual capacity forward edge flow f capacity c e e 2 7 / 9 7 backward edge 51 v v w wFlow edge: Java implementation public class FlowEdge private final int v, w; // from and to private final double capacity; // capacity flow variable private double flow; // flow (mutable) public FlowEdge(int v, int w, double capacity) this.v = v; this.w = w; this.capacity = capacity; public int from() return v; public int to() return w; public double capacity() return capacity; public double flow() return flow; public int other(int vertex) if (vertex == v) return w; else if (vertex == w) return v; else throw new IllegalArgumentException(); public double residualCapacityTo(int vertex) ... next slide public void addResidualFlowTo(int vertex, double delta) ... 52Flow edge: Java implementation (continued) public double residualCapacityTo(int vertex) forward edge if (vertex == v) return flow; else if (vertex == w) return capacity flow; backward edge else throw new IllegalArgumentException(); public void addResidualFlowTo(int vertex, double delta) if (vertex == v) flow = delta; forward edge else if (vertex == w) flow += delta; backward edge else throw new IllegalArgumentException(); residual capacity forward edge flow f capacity c e e 2 7 / 9 7 backward edge 53 v v w wFlow network API public class FlowNetwork public class FlowNetwork FlowNetwork(int V) FlowNetwork(int V) create an empty flow network with V vertices FlowNetwork(In in) FlowNetwork(In in) construct flow network input stream void addEdge(FlowEdge e) addEdge(FlowEdge e) add flow edge e to this flow network IterableFlowEdge adj(int v) adj(int v) forward and backward edges incident to v IterableFlowEdge edges() edges() all edges in this flow network int V() V() number of vertices int E() E() number of edges String toString() toString() string representation Conventions. Allow selfloops and parallel edges. 54Flow network: Java implementation public class FlowNetwork same as EdgeWeightedGraph, private final int V; but adjacency lists of private BagFlowEdge adj; FlowEdges instead of Edges public FlowNetwork(int V) this.V = V; adj = (BagFlowEdge) new BagV; for (int v = 0; v V; v++) adjv = new BagFlowEdge(); public void addEdge(FlowEdge e) int v = e.from(); int w = e.to(); adjv.add(e); add forward edge adjw.add(e); add backward edge public IterableFlowEdge adj(int v) return adjv; 55Flow network: adjacencylists representation Maintain vertexindexed array of FlowEdge lists (use Bag abstraction). tinyFN.txt references to the same FlowEdge object 0 2 3.0 1.0 0 1 2.0 2.0 V adj 6 E 8 0 1 4 1.0 0.0 1 3 3.0 2.0 0 1 2.0 2.0 0 1 2.0 1 0 2 3.0 2 4 1.0 1.0 2 3 1.0 0.0 0 2 3.0 1.0 2 1 3 3.0 1 4 1.0 3 3 5 2.0 2.0 2 3 1.0 0.0 1 3 3.0 2.0 2 3 1.0 4 2 4 1.0 5 3 5 2.0 4 5 3.0 1.0 2 4 1.0 1.0 1 4 1.0 0.0 4 5 3.0 4 5 3.0 1.0 3 5 2.0 2.0 Bag objects Flow network representation Note. Adjacency list includes edges with 0 residual capacity. (residual network is represented implicitly) 56Finding a shortest augmenting path (cf. breadthfirst search) private boolean hasAugmentingPath(FlowNetwork G, int s, int t) edgeTo = new FlowEdgeG.V(); marked = new booleanG.V(); QueueInteger queue = new QueueInteger(); queue.enqueue(s); markeds = true; while (queue.isEmpty()) int v = queue.dequeue(); for (FlowEdge e : G.adj(v)) found path from s to w in the residual network int w = e.other(v); if (markedw (e.residualCapacityTo(w) 0) ) edgeTow = e; save last edge on path to w; markedw = true; mark w; queue.enqueue(w); add w to the queue is t reachable from s in residual network return markedt; 57FordFulkerson: Java implementation public class FordFulkerson private boolean marked; // true if sv path in residual network private FlowEdge edgeTo; // last edge on sv path private double value; // value of flow public FordFulkerson(FlowNetwork G, int s, int t) compute edgeTo value = 0.0; while (hasAugmentingPath(G, s, t)) compute bottleneck capacity double bottle = Double.POSITIVEINFINITY; for (int v = t; v = s; v = edgeTov.other(v)) bottle = Math.min(bottle, edgeTov.residualCapacityTo(v)); for (int v = t; v = s; v = edgeTov.other(v)) edgeTov.addResidualFlowTo(v, bottle); augment flow value += bottle; private boolean hasAugmentingPath(FlowNetwork G, int s, int t) / See previous slide. / public double value() return value; public boolean inCut(int v) is v reachable from s in residual network return markedv; 586.4 MAXIMUM FLOW introduction ‣ FordFulkerson algorithm ‣ maxflowmincut theorem ‣ Algorithms analysis of running time ‣ Java implementation ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu applications ‣Maxflow and mincut applications Maxflow/mincut is a widely applicable problemsolving model. Data mining. Openpit mining. Bipartite matching. Network reliability. Baseball elimination. Image segmentation. liver and hepatic vascularization segmentation Network connectivity. Distributed computing. Security of statistical data. Egalitarian stable matching. Multicamera scene reconstruction. Sensor placement for homeland security. Many, many, more. 60Bipartite matching problem N students apply for N jobs. bipartite matching problem Each gets several offers. 1 Alice 6 Adobe Adobe Alice Amazon Bob Google Carol 2 Bob 7 Amazon Adobe Alice Amazon Bob 3 Carol Dave Adobe Eliza 8 Facebook Facebook Google Carol Is there a way to match all students to jobs 4 Dave 9 Google Amazon Alice Yahoo Carol 5 Eliza 10 Yahoo Amazon Dave Yahoo Eliza 61Bipartite matching problem Given a bipartite graph, find a perfect matching. perfect matching (solution) bipartite graph bipartite matching problem 1 Alice 6 Adobe 1 6 Alice —— Google Adobe Alice Bob —— Adobe Amazon Bob Google Carol 2 7 Carol —— Facebook 2 Bob 7 Amazon Dave —— Yahoo Adobe Alice Amazon Bob Eliza —— Amazon 3 8 3 Carol Dave Adobe Eliza 8 Facebook Facebook 4 9 Google Carol 4 Dave 9 Google Amazon Alice 5 10 Yahoo Carol 5 Eliza 10 Yahoo N students N companies Amazon Dave Yahoo Eliza 62Network flow formulation of bipartite matching Create s, t, one vertex for each student, and one vertex for each job. Add edge from s to each student (capacity 1). Add edge from each job to t (capacity 1). Add edge from student to each job offered (infinite capacity). flow network bipartite matching problem 1 Alice 6 Adobe 1 6 Adobe Alice Amazon Bob Google Carol 2 7 2 Bob 7 Amazon Adobe Alice Amazon Bob s t 3 8 3 Carol Dave Adobe Eliza 8 Facebook Facebook 4 9 Google Carol 4 Dave 9 Google Amazon Alice 5 5 10 Yahoo Carol 5 Eliza 10 Yahoo N students N companies Amazon Dave Yahoo Eliza 63Network flow formulation of bipartite matching 11 correspondence between perfect matchings in bipartite graph and integervalued maxflows of value N. flow network bipartite matching problem 1 Alice 6 Adobe 1 6 Adobe Alice Amazon Bob Google Carol 2 7 2 Bob 7 Amazon Adobe Alice Amazon Bob s t 3 8 3 Carol Dave Adobe Eliza 8 Facebook Facebook 4 9 Google Carol 4 Dave 9 Google Amazon Alice 5 5 10 Yahoo Carol 5 Eliza 10 Yahoo N students N companies Amazon Dave Yahoo Eliza 64What the mincut tells us Goal. When no perfect matching, explain why. 1 6 S = 2, 4, 5 2 2 7 7 T = 7, 10 student in S 3 8 can be matched only to companies in T 4 4 9 S T 5 10 5 10 no perfect matching exists 65What the mincut tells us Mincut. Consider mincut (A, B). Let S = students on s side of cut. Let T = companies on s side of cut. Fact: S T ; students in S can be matched only to companies in T. 1 6 S = 2, 4, 5 2 2 7 7 T = 7, 10 student in S s s t 3 8 can be matched only to companies in T 4 4 9 S T 5 5 10 5 10 no perfect matching exists Bottom line. When no perfect matching, mincut explains why. 66Baseball elimination problem Q. Which teams have a chance of finishing the season with the most wins i team team wins losses to play ATL PHI NYM MON 0 Atlanta 83 71 8 – 1 6 1 1 Philly 80 79 3 1 – 0 2 2 New York 78 78 6 6 0 – 0 3 Montreal 77 82 3 1 2 0 – Montreal is mathematically eliminated. Montreal finishes with ≤ 80 wins. Atlanta already has 83 wins. 67Baseball elimination problem Q. Which teams have a chance of finishing the season with the most wins i team team wins losses to play ATL PHI NYM MON 0 Atlanta 83 71 8 – 1 6 1 1 Philly 80 79 3 1 – 0 2 2 New York 78 78 6 6 0 – 0 3 Montreal 77 82 3 1 2 0 – Philadelphia is mathematically eliminated. Philadelphia finishes with ≤ 83 wins. Either New York or Atlanta will finish with ≥ 84 wins. Observation. Answer depends not only on how many games already won and left to play, but on whom they're against. 68Baseball elimination problem Q. Which teams have a chance of finishing the season with the most wins i team team wins losses to play NYY BAL BOS TOR DET 0 New York 75 59 28 – 3 8 7 3 1 Baltimore 71 63 28 3 – 2 7 4 2 Boston 69 66 27 8 2 – 0 0 3 Toronto 63 72 27 7 7 0 – 0 4 Detroit 49 86 27 3 4 0 0 – AL East (August 30, 1996) Detroit is mathematically eliminated. Detroit finishes with ≤ 76 wins. Wins for R = NYY, BAL, BOS, TOR = 278. Remaining games among NYY, BAL, BOS, TOR = 3 + 8 + 7 + 2 + 7 = 27. Average team in R wins 305/4 = 76.25 games. 69Baseball elimination problem: maxflow formulation Intuition. Remaining games flow from s to t. 0–1 games left team 2 can still win 0–2 0 between 1 and 2 this many more games 0–3 1 ∞ g 1–2 2 w + r – w t s 12 ∞ 4 4 2 1–3 3 team vertices (each team other than 4) 2–3 game vertices (each pair of teams other than 4) Fact. Team 4 not eliminated iff all edges pointing from s are full in maxflow. 70Maximum flow algorithms: theory (Yet another) holy grail for theoretical computer scientists. year method worst case discovered by 3 1951 Dantzig simplex E U 2 1955 FordFulkerson augmenting path E U 3 1970 Dinitz, EdmondsKarp shortest augmenting path E 2 1970 Dinitz, EdmondsKarp fattest augmenting path E log E log( E U ) 5/2 1977 Cherkasky blocking flow E 7/3 1978 Galil blocking flow E 2 1983 SleatorTarjan dynamic trees E log E 2 1985 Gabow capacity scaling E log U 3/2 1997 GoldbergRao length function E log E log U 2 2012 Orlin compact network E / log E E maxflow algorithms for sparse digraphs with E edges, integer capacities between 1 and U 71Maximum flow algorithms: practice Warning. Worstcase orderofgrowth is generally not useful for predicting or comparing maxflow algorithm performance in practice. 3/2 Best in practice. Pushrelabel method with gap relabeling: E . On Implementing PushRelabel Method for the Maximum Flow Problem EUROPEAN JOURNAL OF OPERATIONAL Boris V. Cherkassky 1 and Andrew V. Goldberg 2 RESEARCH ELSEVIER European Journal of Operational Research 97 (1997) 509542 1 Central Institute for Economics and Mathematics, Krasikova St. 32, 117418, Moscow, Russia chereemi.msk.su Theory and Methodology 2 Computer Science Department, Stanford University Stanford, CA 94305, USA Computational investigations of maximum flow algorithms goldberg cs. stanford, edu Ravindra K. Ahuja a, Murali Kodialam b, Ajay K. Mishra c, James B. Orlin d,. a Department t'lndustrial and Management Engineering. Indian Institute of Technology. Kanpur, 208 016, India Abstract. We study efficient implementations of the pushrelabel method b AT T Bell Laboratories, Holmdel, NJ 07733, USA for the maximum flow problem. The resulting codes are faster than the c KA'FZ Graduate School of Business, University of Pittsburgh, Pittsburgh, PA 15260, USA previous codes, and much faster on some problem families. The speedup d Sloun School of Management, Massachusetts Institute of Technology. Cambridge. MA 02139. USA is due to the combination of heuristics used in our implementations. We Received 30 August 1995; accepted 27 June 1996 also exhibit a family of problems for which the running time of all known methods seem to have a roughly quadratic growth rate. Abstract 1 Introduction The maximum flow algorithm is distinguished by the long line of successive contributions researchers have made in obtaining algorithms with incrementally better worstcase complexity. Some, but not all, of these theoretical improvements The rnaximum flow problem is a classical combinatorial problem that comes up have produced improvements in practice. The purpose of this paper is to test some of the major algorithmic ideas developed in the recent years and to assess their utility on the empirical front. However, our study differs from previous studies in in a wide variety of applications. In this paper we study implementations of the several ways. Whereas previous studies focus primarily on CPU time analysis, our analysis goes further and provides 72 pushrdabel 13, 17 method for the problem. detailed insight into algorithmic behavior. It not only observes how algorithms behave but also tries to explain why The basic methods for the maximum flow problem include the network sim algorithms behave that way. We have limited our study to the best previous maximum flow algorithms and some of the plex method of Dantzig 6, 7, the augmenting path method of Ford and Flker recent algorithms that are likely to be efficient in practice. Our study encompasses ten maximum flow algorithms and five classes of networks. The augmenting path algorithms tested by us include Dinic's algorithm, the shortest augmenting path son 12, the blocking flow method of Dinitz 10, and the pushrelabel method algorithm, and the capacityscaling algorithm. The preflowpush algorithms tested by us include Karzanov's algorithm, three of Goldberg and Tarjan 14, 17. (An earlier algorithm of Cherkassky 5 has implementations of GoldbergTarjan's algorithm, and three versions of AhujaOrlinTarjan's excessscaling algorithms. many features of the pushrelabel method.) The best theoretical time bounds Among many findings, our study concludes that the preflowpush algorithms are substantially faster than other classes of for the maximum flow problem, based on the latter method, are as follows. An algorithms, and the highestlabel preflowpush algorithm is the fastest maximum flow algorithm for which the growth rate in algorithm of Goldberg and Tarjan 17 runs in O(nm log(n2/m)) time, an algo the computational time is O(n LS) on four out of five of our problem classes. Further, in contrast to the results of the worstcase analysis of maximum flow algorithms, our study finds that the time to perform relabel operations (or constructing rithm of King et. al. 21 runs in O(nm + n TM) time for any constant e 0, the layered networks) takes at least as much computation time as that taken by augmentations and/or pushes. © 1997 an algorithm of Cheriyan et. al. 3 runs in O(nm + (nlogn) 2) time with high Published by Elsevier Science B.V. probability, and an algorithm of Ahuja et. al. 1 runs in O (am log ( + 2)) time. Prior to the pushrelabel method, several studies have shown that Dinitz' 1. Introduction among mathematicians, operations researchers and algorithm 10 is in practice superior to other methods, including the network computer scientists. simplex method 6, 7, Fordgiflkerson algorithm 11, 12, Karzanov's algorithm The maximum flow problem is one of the most The maximum flow problem arises in a wide 20, and Tarjan's algorithm 23. See e.g. 18. Several recent studies (e.g. 2, fundamental problems in network optimization. Its variety of situations. It occurs directly in problems as intuitive appeal, mathematical simplicity, and wide diverse as the flow of commodities in pipeline net Andrew V. Goldberg was supported in part by NSF Grant CCR9307045 and a applicability has made it a popular research topic works, parallel machine scheduling, distributed com grant from Powell Foundation. This work was done while Boris V. Cherkassky was puting on multiprocessor computers, matrix round visiting Stanford University Computer Science Department and supported by the ing problems, the baseball elimination problem, and abovementioned NSF and Powell Foundation grants. Corresponding author. the statistical security of data. The maximum flow 03772217/97/17.00 © 1997 Published by Elsevier Science B.V. All rights reserved. PII S03772217(96)00269X Summary Mincut problem. Find an stcut of minimum capacity. Maxflow problem. Find an stflow of maximum value. Duality. Value of the maxflow = capacity of mincut. Proven successful approaches. FordFulkerson (various augmentingpath strategies). Preflowpush (various versions). Open research challenges. Practice: solve realworld maxflow/mincut problems in linear time. Theory: prove it for worstcase inputs. Still much to be learned 73
Website URL
Comment
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.BenjaminClark
User Type:
Teacher
Country:
United States
Uploaded Date:
21-07-2017