Differences

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

--- courses:cs211:winter2011:journals:chen:chapter_7 [2011/04/06 17:37] – created zhongc
+++ courses:cs211:winter2011:journals:chen:chapter_7 [2011/04/06 20:59] (current) – [7.3 Choosing Good Augmenting Paths] zhongc
@@ Line 21: / Line 21: @@
 o There is a single source node s e V.
 o There is a single sink node t ~ V
+The Problem:
+The Maximum-Flow Problem Given a flow network, the goal is to
+arrange the traffic so as to make as efficient use as possible of the available
+capacity.
+Thus the basic algorithmic problem we will consider is the following:
+Given a flow network, find a flow of maximum possible value
+Attempt: Greedy - local informatioon is not enough to solve for global optimum
+We can define the Residual Graph, which provides a systematic way to search for forward-backward operations in order to find the maximum flow.
+Given a flow network , and a flow  on , we define the residual graph  of  with respect to  as follows.
+. The node set of  is the same as that of G
+. Each edge  of  is with a capacity of c(e)-f(e).
+. Each edge  of  is with a capacity of f(e).flipped over.
+====== 7.2 Maximum Flows and Minimum Cuts in a Network ======
+goal is to show that the flow that is returned by the Ford-F~kerson
+Algorithm has the maximum possible value of any flow in G.Prove optimality.
+find the min cut:
+Find an s-t cut of minimum capacity
+flow value lemma/pf --- the idea of flow conservation
+Corollary. Let f be any flow, and let (A, B) be
+any cut. If v(f) = cap(A, B), then f is a max
+flow and (A, B) is a min cut.
+f is an s-t-flow such that there is no s-t path in the residual graph
+then there is an s-t cut (A*,B*) in G for which v(f) = c(A*, B*). Consequently,
+f has the maximum value of any flow in G, and (A*, B*) has the minimum
+capacity of any s-t cut in G.
+useful lemma,
+Let f be any s-t flow, and (A,B) any s-t cut. Then v(f) =fin(B) -f°Ut(B).
+Pf on P374.
+If f is an s-t-flow such that there is no s-t path in the residual graph
+then there is an s-t cut (A*,B*) in G for which v(f) = c(A*, B*). Consequently,
+f has the maximum value of any flow in G, and (A*, B*) has the minimum
+capacity of any s-t cut in G. .....
+Proof. The statement claims the existence of a cut satisfying a certain desirable
+property; thus we must now identify such a cut. To this end, let A* denote the
+set of all nodes v in G for which there is an s-v path in @. Let B* denote.~e
+set of all other nodes: B* = V - A*.
+Runtime analysis:
+O(Cm)
+Intereting/readable: 6/6
+====== 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