Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2018:journals:patelk:chapter7 [2018/03/31 14:29] – [7.2 Maximum Flows and Minimum cuts in a Network] patelk
+++ courses:cs211:winter2018:journals:patelk:chapter7 [2018/03/31 17:53] (current) – [7.7 Extensions to the Maximum-Flow Problem] patelk
@@ Line 142: / Line 142: @@
 Readability: 6.5
 Interesting: 6.5
+----
+===== 7.5 A First Application: The Bipartite Matching Problem =====
+__Analyzing the Algorithm: Flows and Cuts__
+**The Problem**
+  * Bipartite Graph G = (V,E) is an undirected graph whose node set can be partitioned as V = X union Y, with the property that every edge e in E has one end in X and the other in Y
+  * Matching M in G is a subset on the edge M in E such that each node appears in at most one edge in M
+**Designing the Algorithm**
+  * We construct a flow network G'
+  * Direct all edges in G from X to Y
+  * Add a node s, and an edge (s,x) from s to each node in X
+  * add a node t, and an edge (y,t) from each node in Y to t
+  * Give each edge in G' a capacity of 1
+  * Compute a maximum s-t flow in the network G'
+**Analyzing the Algorithm**
+  * Suppose there is a matching in G consisting of k edges
+  * Then consider the flow f that sends one unit along each path, that is f(e) = 1 for each ege on one of these paths
+  * Suppose there is a flow f' in G' of value k
+  * By the integrality theorem for maximum flows, we know there is an integer-valued flow f of value k
+  * Since all capacities are 1, f(e) is equal to either 0 or 1 for each edge e
+  * Consider the set M' of edges in the form (x,y) on which the flow value is 1
+    * M' contains k edges
+    * Each node in X is the tail of at most one edge in M'
+    * Each node in Y is the head of at most one edge in M'
+  * If we view M' as a set of edges in the original bipartite graph G, we get a matching of size k:
+    * The size of the maximum matching in G is equal to the value of the maximum flow in G'; and the edges in such a matching in G are the edges that carry flow from X to Y in G'
+  * //Bounding the Running Time//
+    * The Ford-Fulkerson Algorithm can be used to find a maximum matching in a bipartite graph in O(mn) time
+      * Consider the matching M consisting of edges in the bipartite graph
+        * Let f be the corresponding flow in G'
+        * Matching in not maximum, so f is not a maximum s-t flow, and hence there is an augmenting path in the residual graph G'f.
+        * All augmenting paths must alternate between edged used backward and forward, as all edges of the graph G' go from X to Y
+          * also known as alternating paths in the context of finding a maximum matching
+        * Effect of this augmentation is to take the edges used backward out of the matching and replace them with the edges going forward.
+          * Because the path goes from s to t, there is one more forward edge than backward edge (size of the matching increases by one)
+__Extensions: The Structure of Bipartite Graphs with No Perfect Matching__
+  * What if there is not a perfect matching?
+  * We can decide if the graph G has a perfect matching by checking if the maximum flow in a related graph G' has at least n
+    * By the Max-Flow Min-Cut Theorem, there will be an s-t cut of capacity less than n if the maximum-flow value in G' has value less than n
+      * a cut with capacity less than n provides a "certificate" of no matching
+  * If a bipartite graph G = (V,E) with two sides X and Y has a perfect matching, then for all A in X, we must have |Gamma(A)| >= |A|
+    * Hall's Theorem
+  * Assume that the bipartite graph G = (V,E) has two sides X and Y such that |X| = |Y|. Then the graph G either has a perfect matching or there is a subset A in X such that |Gamma(A)| < |A|.
+    * A perfect matching or an appropriate subset A can be found in O(mn) time
+{{:courses:cs211:winter2018:journals:patelk:mincutmovingnodes.png?nolink&400|}}
+==== Personal Thoughts ====
+This section was more dense, so it was not quite as easy to read. I think this section spent a lot of time trying to prove theorems, and as a result, I had to spend more time processing and learning this section. However, on the whole, I think everything this section says made sense to me. I know I'll need some application practice in order to fully comprehend this section.
+Readability: 6.0
+Interesting: 6.0
+----
+===== 7.7 Extensions to the Maximum-Flow Problem =====
+  * Many problems have a nontrivial combinatorial search component that can be solved in polynomial time
+**The Problem: Circulations with Demands**
+  * set S of sources generating flow and set T of sinks that can absorb flow
+  * Consider a problem where sources have fixed supply values and sinks have fixed deman values
+  * goal: ship flow from nodes with available supply to those with given demands
+  * Associated with each node v in V is a demand dv
+    * If dv > 0, the node v has a demand of dv for flow
+    * Node is a sink and it wishes to receive dv units more flow than it sends out
+    * If dv < 0, the node v has a supply of -dv; the node is a source and it wishes to send out -dv units more flow than it receives
+    * If dv = 0: node v is neither a source nor a sink
+      * Assume all capacities and demands are integers
+  * S: set of all nodes with negative demand
+  * T: set of all nodes with positive demand
+  * Circulation with demands {dv} is a function f that assigns a nonnegative real number to each edge and satisfies the following two conditions:
+    * Capacity: for each e in E, we have 0 <= f(e) <= ce
+    * Demand: for each v in V, we have v, fin(v)-fout(v) = dv
+  * Feasibility Problem: does there exist a circulation that meets the two conditions above?
+  * If there exists a feasible circulation with demands {dv}, then sum of the demands = 0
+**Designing and Analyzing an Algorithm for Circulations**
+  * We can reduce the problem of finding a feasible circulation with demands {dv} to the problem of finding a maximum s-t flow in a different network
+  * We attach a "super-source" s* to each node in S and a "super-sink" t* to each node in T
+    * create a graph G' from G by adding new nodes s* and t* to G
+    * for each node v in T, we add an edge (v,t*) with capacity dv
+    * for each node u in S, we add an edge (s*, u) with capacity du
+    * carry the remaining structure of G over to G' unchanged
+  * Can think of this reduction as introducing a node s* that "supplies" all the sources with their extra flow, and a node t* that "siphons" the extra flow out of the sinks.
+  * There cannot be an s*-t* flow in G' of value greater than D, since the cut (A,B) with A ={s*} only has capacity D
+    * Further, if there is a flow of value D in G', there there is such a flow that takes integer values
+  * There is a feasible circulation with demands {dv} in G if and only if the maximum s*-t* flow in G' has value D. If all capacities and demands in G are integers, and there is a feasible circulation, there there is a feasible circulation that is integer-valued
+  * The graph G has a feasible circulation with demands {dv} if and only if for all cuts (A,B), the sum of for all v in B of dv <= c(A,B).
+**The Problem: Circulations with Demands and Lower Bounds**
+  * To force the flow to make use of certain edges, we can enforce lower bounds on edges
+  * G=(V,E) with a capacity of ce and a lower bound le on each edge e
+  * -<= le <= ce for each e
+  * each node v also has a demand dv (positive or negative)
+  * all are integers
+  * circulation in flow network must satisfy two conditions:
+    * Capacity: for each e in E, we have le<=f(e)<=ce
+    * Demand: for every v in V, we have fin(v)-fout(v) = dv
+**Designing and Analyzing an Algorithm with Lower Bounds**
+  * Reduce this to the problem of finding a circulation with demands but no lower bounds
+  * On each edge e, we need to sent at least le units of flow
+  * Initial circulation: f0(e) = le
+    * f0 satisfies all the capacity conditions (both lower and upper bounds)
+  * If Lv = dv, where Lv is quantity, then we have satisfied the demand condition at v
+  * If not, then we need to superimpose a circulation f1 on top of f0 that will clear the remaining "imbalance" at v
+    * f1in(v)-f1out(v) = sum of all e into v of le = the sum of a v of le
+  * There is a feasible circulation in G if and only if there is a feasible circulation in G'
+    * If all demands, capacities, and lower bounds in G are integers and there is a feasible circulation, then there is a feasible circulation that is integer-valued.
+==== Personal Thoughts ====
+This section took the concept of network flows to the next level by bringing in other variations/extensions of the original problem. While the overarching problems made sense, I got bogged down in a lot of the terminology and new factors that were added in. I think I need to reread this section one more time after we go over it in class to fully grasp the concepts presented in this section.
+Readability: 5.5
+Interesting: 5.5