Differences

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

--- courses:cs211:winter2011:journals:wendy:chapter7 [2011/04/04 04:17] – [Section 2: Maximum Flows and Minimum Cuts in a Network] shangw
+++ courses:cs211:winter2011:journals:wendy:chapter7 [2011/04/04 05:39] (current) – [Section 3: Choosing Good Augmenting Paths] shangw
@@ Line 28: / Line 28: @@
 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.