Differences

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

--- courses:cs211:winter2018:journals:martineza:home [2018/04/03 00:34] – [Section 7.7:] martineza
+++ courses:cs211:winter2018:journals:martineza:home [2018/04/03 01:08] (current) – [Section 7.7: Extensions to Maximum Flow] martineza
@@ Line 409: / Line 409: @@
 **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?