Differences

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

--- courses:cs211:winter2018:journals:patelk:chapter7 [2018/03/31 15:25] – [7.5 A First Application: The Bipartite Matching Problem] patelk
+++ courses:cs211:winter2018:journals:patelk:chapter7 [2018/03/31 17:53] (current) – [7.7 Extensions to the Maximum-Flow Problem] patelk
@@ Line 203: / Line 203: @@
 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