Differences

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

--- courses:cs211:winter2012:journals:richard:trembleinfearmortal [2012/04/04 03:52] – created marmorsteinr
+++ courses:cs211:winter2012:journals:richard:trembleinfearmortal [2012/04/04 04:02] (current) – Added last section and readability ratings marmorsteinr
@@ Line 8: / Line 8: @@
 The number can't be greater than the edge's capacity in the flow network, and also sum of the flow numbers coming into each node has to equal the sum of the flow numbers going out, except for the sink and source. After a few false starts trying to design the algorithm, (dynamic programming? Nope. Greedy? Nope) they get around to outlining Ford-Fulkerson, with the residual graph and all the goodies we covered in lecture. They prove that after every augmentation the graph remains--and use that and some other things to prove the algorithm terminates. It's pretty exciting.
+Readability 8/10
 ==7.2==
 Well if I thought the last section was jam-packed of analysis about maximum flows and the Ford-Fulkerson algoritm, boy was I in for a surprise because this section takes it to the extreme. First it formalizes the notion of s-t cuts, and proves useful properties about them, like the difference between the values of the edges out of a cut plus the sum of the values of the edges into the cut equals the value of the cut, which is used to prove that the capacity of the cut forms an upper bound on the value of the flow. Then en route to proving the optimality of the Ford-Fulkerson algorithm they prove that the max flow equals the min cut. Interesting thing they point out--they prove that with integers the FF algorithm terminates, but it's possible, they say, to have "pathological" choices if you widen it to reals, because it could augment by just a smaller and smaller amont each time.
+Readability 6/10
+It was a bit difficult figuring out what they were always trying to say through the formalism. I'd always have to go back and look what like v(f) meant which they defined in like the first section--it's just hard to keep track of all the symbols.
 ==7.5==
@@ Line 17: / Line 22: @@
 Then it proves something interesting about "certificates" indicating whether a particular bipartite graph has a perfect matching or not. It turns out that, if there's no perfect matching, you'll always be able to find a set of nodes on one side of the bipartite graph which is larger than the set of nodes on the other side which have edges to nodes in the first set--and such always implies the abscence of a perfect matching. Kind of neat.
+Readability 7/10
+==7.7==
+This section is about circulation, where in addition to capacity you have a circulation. So, a circulation assigns a real number to every edge like a flow, but the requirement here is that instead of requiring that the flow in be equal to the flow out, you just take the flow in minus the flow out and call that number the demand value (or supply, if it's negative). And then the problem here, instead of maximizing, is trying to find a way to make total supply equal total demand (find a "feasible circulation". The solution, like we talked about in class, is take all the supply nodes and hook them up to a "super-source" node and take the demanders and hook them up to a "super-sink" (don't those sound like awesome superhero/supervillain names? I thought not.) Anyway, if there's anyway you can get all the flow to the sink from the source, given the capacities in the graph, that means there is a feasible circulation. And the chapter covers putting restrictions on the demands.
+Readability 8/10