Differences

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

--- courses:cs211:winter2011:journals:chen:chapter_7 [2011/04/06 19:32] – [7.2 Maximum Flows and Minimum Cuts in a Network] zhongc
+++ courses:cs211:winter2011:journals:chen:chapter_7 [2011/04/06 20:59] (current) – [7.3 Choosing Good Augmenting Paths] zhongc
@@ Line 84: / Line 84: @@
+====== 7.3 Choosing Good Augmenting Paths ======
+Big idea: Good choice of augmentation path can improve bounds significantly.
+augmentation increases the value of the maximum
+flow by the bottleneck capacity of the selected path; so if we choose paths
+with large bottleneck capacity, we will be making a lot of progress.
+maintain a so-called scaling parameter to avoid looking at exactly the largest bottleneck
+P379
+The algorithms on  p380
+analysis of the running time:
+The number of iterations o[ the outer While loop is at most 1 +[log2 C].
+we are using paths that augment the flow by a great amount, and so there should be relatively few augmentations.
+Let f be the [low at the end of the A-scaling phase. There is an s-t
+cut (A, B) in G for which c(A, B) < v(f) + mA, where m is the number of edges
+in the graph G. Consequently, the maximum [low in the network has value at
+most v(f) + m A.
+Proof on P380.
+Interesting/readable: 5/6