Differences

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

--- courses:cs211:winter2011:journals:camille:chapter7 [2011/04/05 04:17] – [Section 2: Max Flows and Min Cuts in a Network] cobbc
+++ courses:cs211:winter2011:journals:camille:chapter7 [2011/04/05 04:39] (current) – [Section 2: Max Flows and Min Cuts in a Network] cobbc
@@ Line 11: / Line 11: @@
 ===== Section 2:  Max Flows and Min Cuts in a Network =====
-   * **Summary:**
+    * **Summary:**
-It's important for the running time of this algorithm that you pick good augmenting paths. They give an example of when choosing the wrong path could be especially bad. So in order to do make a running time improvement, we need to choose paths with high bottlenecks first (that way we make the most "progress" toward the max flow in each step). But instead of trying to find the one with the highest bottleneck capacity, we maintain a "scaling parameter" delta and look for paths with a bottleneck of at least delta. So we keep track of the residual graph that only has edges of at most delta capacity. Delta starts out as a the highest power of two that is no larger than the maximum capacity out of s, and after we've found all of the augmenting paths in the residual graph of that delta, we divide delta by two and repeat (see algorithm p353). This is really just another implementation of Ford-Fulkerson (i.e. it will still work!), and it's bounded by an O((m^2)(logC)) running time. This is because every augmentation in the delta-scaling phase increases the flow value by at least delta, and the max flow in the network has value at most v(f)+m*delta. It makes sense to look for an algorithm with a running time that only depends on m and n (instead of C). Some have been found that run in O(mnlogn), O(n^3), etc ... that's called strongly polynomial, and it's discussed in the next section.
+This section is an analysis of the Ford-Fulkerson algorithm. They show that the flow is the max possible value for any flow in the graph. If you divide the nodes into two sets A and B such that s is in A and t is in B, then the capacity of the cut is the sum of the capacities of the edges out of A. Cuts provide upper bounds on the values of flows. v(f) = fout(A)-fin(A). They go on to show that the max flow is upper bounded by the capacity of every cut, so there can't be a cut with value less than the flow. In order to show that the flow is the maximum psosible value of any flow in G, we use this fact. We show that there's some cut where the flow is equal to the value of the cut. That means that the flow is max and that that particular cut is min. They prove that this is the case and that this is all that's necessary to show that F-F is optimal. The residual graph from F-F will also give us the min cut pretty directly. It's all of the nodes reachable from s. There's a flow and a cut in every flow network such that their values are equal (pretty cool!), and the max value of an s-t flow is equal to the capacity of an s-t cut in every flow network. Integers vs. real numbers: for rational numbers, you can multiply by some constant to turn the whole thing into integers. No biggie. But irrational numbers create a little bit more of a problem (ok ... a big problem): the F-F might not terminate! But the max-cut-min-flow thing still works. In real problems, there wouldn't be irrational numbers, but the F-F can take a long time to complete if we don't make good choices of augmenting paths. That's improved upon in the next section.
     * **Questions and Insights:**
@@ Line 19: / Line 19: @@
     * **Readability:**
-Great :)
+Great :) Except I felt like they kept giving the same facts over and over and over in this section ... they're all so closely related and follow pretty directly from each other.
 ===== Section 3:  Choosing Good Augmenting Paths =====
+  * **Summary:**
-    * **Summary:**
+It's important for the running time of this algorithm that you pick good augmenting paths. They give an example of when choosing the wrong path could be especially bad. So in order to do make a running time improvement, we need to choose paths with high bottlenecks first (that way we make the most "progress" toward the max flow in each step). But instead of trying to find the one with the highest bottleneck capacity, we maintain a "scaling parameter" delta and look for paths with a bottleneck of at least delta. So we keep track of the residual graph that only has edges of at most delta capacity. Delta starts out as a the highest power of two that is no larger than the maximum capacity out of s, and after we've found all of the augmenting paths in the residual graph of that delta, we divide delta by two and repeat (see algorithm p353). This is really just another implementation of Ford-Fulkerson (i.e. it will still work!), and it's bounded by an O(m^2(logC)) running time. This is because every augmentation in the delta-scaling phase increases the flow value by at least delta, and the max flow in the network has value at most v(f)+m*delta. It makes sense to look for an algorithm with a running time that only depends on m and n (instead of C). Some have been found that run in O(mnlogn), O(n^3), etc ... that's called strongly polynomial, and it's discussed in the next section.
     * **Questions and Insights:**
+None.
     * **Readability:**
+Wonderful :)