Differences

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

--- courses:cs211:winter2011:journals:wendy:chapter7 [2011/04/04 05:34] – [Section 3: Choosing Good Augmenting Paths] shangw
+++ courses:cs211:winter2011:journals:wendy:chapter7 [2011/04/04 05:39] (current) – [Section 3: Choosing Good Augmenting Paths] shangw
@@ Line 39: / Line 39: @@
 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.
+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.