Differences

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

--- courses:cs211:winter2018:journals:martineza:home [2018/04/03 00:32] – [Section 7.5: Bipartite Matching] martineza
+++ courses:cs211:winter2018:journals:martineza:home [2018/04/03 01:08] (current) – [Section 7.7: Extensions to Maximum Flow] martineza
@@ Line 406: / Line 406: @@
 **REFLECTION:**
 I found this section very difficult to read 4/10, because they used symbols that I have never before, such as the upside down L. I really wish I knew math terminology because I feel like that would make reading this textbook much easier at times. One question I have is: when is Bipartite Matching useful? What real world applications does it relate to? We haven't talked about this problem in class yet, hopefully that will make it clearer.
-====Section 7.7: ====
+====Section 7.7: Extensions to Maximum Flow====
+**SUMMARY:**
+Many problems can be solved in polynomial time because they can be reduced to problems of maximum flow. One such extension is meeting the demand of multiple sinks using the flow produced by multiple sources (eg. multiple factories shipping products to multiple stores). By manipulating the graph and adding a "super" source and "super" sink, we can reduce the problem to essentially a maximum flow problem. If the maximum flow of this new graph has value D, that means there is a feasible circulation -- otherwise, there is none. Another extension is that of forcing the solution to include certain edges by placing lower bounds on edges. We want to know if there is a circulation that satisfies the new conditions created by this limitation. We do this by creating a graph G' that is the same as G but without lower bounds. If G' contains a feasible circulation, that means that G does as well.
+**REFLECTION:**
+I give this section a 7/10. It wasn't super-interesting but it also wasn't terribly complicated like the last couple of sections I've read. I'm interested to see these ideas explained in class -- I feel like some of these concepts would be more clear with step-by-step illustrations. The algorithms we looked at here are for seeing if there exists a way to solve the problem at hand, but can they actually say what the most efficient way is? Do companies actually use algorithms like this to ensure top efficiency in product delivery?