Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2011:journals:charles:chapter7 [2011/04/06 08:02] – [7.2 Maximum Flows and Minimum Cuts in a Network] gouldc | courses:cs211:winter2011:journals:charles:chapter7 [2011/04/06 08:16] (current) – [7.3 Choosing Good Augmenting Paths] gouldc | ||
|---|---|---|---|
| Line 17: | Line 17: | ||
| ===== 7.3 Choosing Good Augmenting Paths ===== | ===== 7.3 Choosing Good Augmenting Paths ===== | ||
| + | Much research is and has been devoted to improving the method by which we choose good augmenting paths, especially in the hope of minimizing the number of iterations for the Maximum-Flow Problem. The authors depict a worse case scenario where the FF Algorithm performs its upper bound number of iterations. The idea behind a solution is to pick large augmenting paths rather than smaller ones, because that improves the flow better. This will reduce the number of iterations, but increase the cost per iteration. To lessen this increase, the new algorithm avoids having to pick the maximum augmentation each time and instead comes with a scaling parameter that picks an augmentation that is deemed large enough. This way the solution will be reached more quickly (in fewer iterations) but without increasing the per-iteration cost too much. | ||
