Differences

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

--- courses:cs211:winter2011:journals:charles:chapter7 [2011/04/06 07:45] – [7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm] gouldc
+++ courses:cs211:winter2011:journals:charles:chapter7 [2011/04/06 08:16] (current) – [7.3 Choosing Good Augmenting Paths] gouldc
@@ Line 6: / Line 6: @@
 Problem outline: Find a maximum flow in a network. Sometimes single s-t paths don't support maximum flow...in these cases we might want to "push forward" on edges with residual capacity, or "push backward" on edges that already have some flow. The point of this augmentation is to divert flow so that more flow can be added to the network without violating conditions. This leads to residual graphs, which look like network graphs but define new capacities (called residual capacities) which are the old capacities minus the current flows through that edge.
-Solution: Function that augments the flow by making use of the various forward edges and backward edges in the residual graph. The Ford-Fulkerson Algorithm, as it's called, builds up the solution from zero flow to maximum flow by augmenting and updating the residual graph until there are no more s-t paths in it. The running time O(mC) because the bound on the number of edges in the residual graph is O(m), and the algorithm can run in at most O(C) iterations, where C is the sum of the capacities out of the source node.
+Solution: Function that augments the flow by making use of the various forward edges and backward edges in the residual graph. The Ford-Fulkerson Algorithm, as it's called, builds up the solution from zero flow to maximum flow by augmenting and updating the residual graph until there are no more s-t paths in it. The running time O(mC) because the upper bounds on the number of edges in the residual graph is O(m), and the algorithm can run in at most O(C) iterations, where C is the sum of the capacities out of the source node.
 ===== 7.2 Maximum Flows and Minimum Cuts in a Network =====
+This section takes a deeper look at the Ford-Furkelson (lol) Algorithm from the last section and proves a bunch of things about it. Furthermore, it introduces the concept of a cut, which is defined as a partition of the vertex set into two subsets such that for the given s-t cut, s is a member of the first partition and t is a member of the second partition. Above all this section proves that "max-flow equals min-cut" (K&T, 348).
+(7.10) FF Algorithm returns a max-flow.
+(7.11) Given a max-flow, min-cut can be computed in O(m) time.
+(7.13) //In every flow network, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut.//
 ===== 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.