Differences

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

--- courses:cs211:winter2018:journals:patelk:chapter7 [2018/03/31 15:44] – [7.7 Extensions to the Maximum-Flow Problem] patelk
+++ courses:cs211:winter2018:journals:patelk:chapter7 [2018/03/31 17:53] (current) – [7.7 Extensions to the Maximum-Flow Problem] patelk
@@ Line 237: / Line 237: @@
     * 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
+----