Differences

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

--- courses:cs211:winter2011:journals:wendy:chapter7 [2011/04/04 03:51] – [Section 1: The Maximum-Flow and the Ford-Fulkerson Algorithm] shangw
+++ courses:cs211:winter2011:journals:wendy:chapter7 [2011/04/04 05:39] (current) – [Section 3: Choosing Good Augmenting Paths] shangw
@@ Line 18: / Line 18: @@
 Readability is 7.
+===== Section 2: Maximum Flows and Minimum Cuts in a Network =====
+The section further continues the analysis of the F-F algorithm.
+If we separate the nodes into two sets, A, B such that s in A, t in B, we denote the s-t cut as (A,B), the capacity of the cut as c(A,B). Two important observations are:
+, f be any s-t flow, (A,B) any cut, v(f)=fout(A)-fin(A) (we can intuitively see it by thinking that all the flow must come across the cut at some pt)
+, Let f be any s-t flow, (A,B) s-t cut, v(f)<=c(A,B). (this can be visualized the same way as the proceeding property)
+Now, we can use some particular (A,B) in a graph-- the one such that c(A,B) having minimum value, to determine the maximum possible flow, which also obviously makes sense. The theorem can be stated as:
+if we can find a flow such that v(f)=c(A,B), for some A,B, then f is the maximum flow and (A,B) the minimum cut.
+The book shows that the F-F gives back the maximum flow, which is also the minimum cut. Hence, in every flow network, there is a flow f and a cut (A,B) so that v(f)=c(A,B),
+Note that all the works so far are under the assumption that the edges' capacities are positive integers. Hence we conclude that if all capacities in the flow network are integers, then there is a maximum flow f for which every flow value f(e) is an integer.
+Then the section goes to discuss the comment I pulled out at the journal of section1: what if non-integer?
+If the capacities are positive rational number, it is not hard to adjust the algorithm-find the least common multiplier and multiply it to everything. However, if just real numbers, it is possible for the algorithm to run forever, since we uses the integer fact to assure the termination of the FF algorithm in section 1. Regardless, the mincut=maxflow theorem still holds in this setting. In addition, in real life, mostly we encounter integer or rational capacities.
+Since the end of the section solves my concern, the readability is 8.
+===== Section 3: Choosing Good Augmenting Paths =====
+Notice that in the journal of section 1, I mentioned if the augmented path P is "efficiently" selected and never really talked about how. Because the entire section 3 is going to contribute to the illustration. Suppose we do not do this efficiently, thus if each augmented path increase the flow by 1, the bound C can be really large.
+The idea is that for each iteration, we hope to gain a flow value as big as possible. The way to do so is that we maintain a scaling parameter and look for paths that have bottleneck capacity of at least that value (by not considering edges whose remaining capacity is lower than that value); if there is no such path, then we reduce the scaling parameter by half. So basically if the parameter is shrunk to 1, then it is the same as increment of 1 in the original method (Gf(delta)=Gf).
+The number of iterations of the outer while loop in the algorithm provided in the book is easy to be seen as O(log_2 C).
+It is not hard to see that during the delta-scaling phase, the increment of the augmentation would promote the flow at least O(delta). Consequently, we have,at delta-scaling phase, the maximum flow in the network has value at most v(f)_mdelta where m is the number of edges in the graph. It follows that the number of augmentations in one scaling phase is at most 2m. Hence we can conclude that the upper bound running time of the F-F algorithm is O(m^2log2C). It is not absolutely in poly time. The next section of the book talks about a different approach that makes the solution strictly poly.
+Readability is 7.