Differences

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

--- courses:cs211:winter2014:journals:deirdre:chapter6 [2014/03/29 19:51] – [6.4] tobind
+++ courses:cs211:winter2014:journals:deirdre:chapter6 [2014/04/02 03:16] (current) – [7.7 - Extensions to the Max-Flow Problem] tobind
@@ Line 133: / Line 133: @@
 **Designing the Algorithm**
+To find out the value for OPT(//n//) we not only need the value of OPT(//n// - ONE), but we also need to know the best solution we can get using a subset of the first //n// - ONE items and total allowed weight //W - wn//. So, we have a ton of subproblems - one for each //i// = 0,...//n// (each request) and each integer 0<=//w//<=//W//. We will use OPT(//i, w//) to denote the value of the optimal solution using a
+subset of the items {ONE,...,//i//} with max allowed wieght //w//.
+If //w < wi// then OPT(//i,w//) = OPT(//i// - ONE,//w//). Otherwise OPT(//i,w//) = max(OPT(//i// - ONE, //w//), //wi// + OPT(//i// - ONE, //w - wi//).
+   Subset-Sum
+    array M[0...n, 0....W]
+    Initialize M[0,w] = 0 for each w = 0, ..., W
+    For i = ONE, 2, ..., n
+      For w = 0, ...,@
+        Use the recurrence above to compute M[i,w]
+      Endfor
+    Endfor
+    Return M[n,W]
+**analyzing the algorithm**
+Like in weighted interval scheduling, we are building up a table of solutions //M// and we compute each of the values //M[i,w]// in //O(ONE)// time using the previous valus. Thus the run time is proportional to the number of entries in the table.  The Subset-Sum(//n, W//) alg correctly computes the optimal value of the problem and runs in //O(nW)// time. Given a table //M// of the optimal values of the subp, the optimal set //S// can be found in //O(n)// time.
+.5. The lecture made more sense so this was kind of just a cursory review of that.
+======7.ONE - The Max-Flow Problem and the Ford-Fulkerson alg ======
+Flow Networks - a directed graph //G = (V, E)// with the following features
+  * associated with each edge //e// is a capacity, which is a nonnegative number that we denote //ce//.
+  * there is a single source node //s// exist in //V//.
+  * there is a single sink node //t// exist in //V//.
+Nodes other than //s// and //t// will be called internal nodes.
+We will make two assumptions: first, no edges enters teh source //s// and no edge leaes the sink //t//; second, that there is at least one edge incident to each node; and third, that all capacities are integers.
+Defining Flow - We say an //s//-//t// flow is a function //f// that maps each edge //e// to a nonnegative real number. The value //f(e)// intuitively represents the amount of flow carried by edge //e//. a flow //f// must satisfy capacity and conservation conditions. The flow of an edge cannot exceed the capacity of the edge. The values of a flow //f//, denoted //v(f)//, is defined to be the amount of flow generated at the source.
+Max-flow Problem - Given a flow network, find a flow of max possible values.
+**Designing the alg**
+To push flow, we can push forward on edges with leftover capacity and push backward on edges that are already carrying flow to divert it in a different direction. We define the residual graph //Gf// of //G// as
+  * the node set of //Gf// is the same as that of //G//
+  * for each edge //e = (u,v)// of //G// on which //f(e) < ce//, the are //ce - f(e)// "leftover" units of capacity on which we could try pushing flow forward so we include the edge //e = (u,v)// in //Gf// with a capaicty of //ce - f(3)//. ->> forward edges
+  * for each edge //e// on which //f(e) > 0//, there are //f(e)// units of flow we can "undo" by pushing backwards. So we include the edge //e' = (v,u)// in //Gf// with a capacity of //f(e)//. ->>> backwards edges
+//Gf// has at most 2x the edges as //G//.
+To augment paths in a residual graph:
+Let //P// be a simple //s-t// path in //Gf//. We define bottleneck(//P,f//) to be the min residual capaicty of any edge on //P//, with respect to the flow //f//. Now,
+   augment(f,P)
+     Let b = bottleneck(P,f)
+     For each edge (u,v) ∈ P
+        If e = (u, v) is a forward edge then
+           increase f(e) in G by b
+        Else ((u,v) is a backward edge and let e = (v,u))
+           decrease f(e) in G by b
+        Endif
+      Endfor
+      Return(f)
+The result of augment(//f,P//) is a new flow //f'// in //G//, obtained by increasing and decreasing the flow values on edges of //P//.
+Now, the alg to compute a //s-t// flow:
+   Max-flow
+     Initially f(e) =0 for all e in G
+     While there is an s-t path in the residual graph Gf
+        Let P be a simple s-t path in Gf
+        f' = augment(f,P)
+        Update f to be f'
+        Update the residual graph Gf to be Gf'
+     Endwhile
+     Return f
+This is the Ford-Fulkerson algorithm.
+**analyzing the algorithm: termination and running time**
+  * at every intermediate stage of the Ford-Fulkerson algorithm, the flow values {f(e)} and the residual capacities in //Gf// are integers.
+  * Let //f// be a flow in //G// and let //P// be a simple //s-t// path in //Gf//. Then //v(f') = v(f) + bottleneck(P,f)// and since //bottleneck(P,f) > 0//, we have //v(f') > v(f)//.
+  * The FF alg terminates in at most //C// iterations of the while loop. C = total possible sum
+  * The FF alg can run in //O(mC)// time.
+This section was a nine out of ten.
+======7.2- Maximum Flows and Minimum Cuts in a network. ======
+**analyzing the algorithm: Flows and Cuts**
+Now we want to show that the flow found by FF has the max possible value of any flow in G.
+Consider dividing the nodes of the graph into two sets, //a// and //B//, so that //s ∈ a// and //t ∈ B//. The capacity fo a cut (//a,B//), which we will denote //c(a,B)// is simply the sum of the capacities of all edges out of //a//.
+Note that if (//a,B//) is a cut, then the edges into //B// are precisely the edges out of //a//. So, we have fout(//a//) = fin(//B//) and fin(//a//) = fout(//B//). So, let //f// be any //s-t// flow and (//a,B//) any //s-t// cut. Then //v(f)// = fin(//B//) - fout(//B//).
+  (7.8) Let f be any s-t flow, and (a,B) any s-t cut. Then v(f) ≤ c(a,B).
+**analyzing the algorithm: Max-Flow equals Min-Cut**
+Let //f//* denote the flow returned by FF. To show that //f//* has the max possible vale of any flow in //G//, we exhibit an //s-t// cut (//a*, B*//) for which //v(f*) = c(a*, B*)//. So f* has the max value and (//a*, B*//) has the min capacity of any //s-t// cut.
+If //f// is an //s-t// flow s.t. there is no //s-t// path in the residual graph //Gf//, then there is an //s-t// cute (//a*, B*//) in //G// for which //v(f) = c(a*, B*)//. Consequently, //f// has the max value of any flow in //G// and (//a*, B*//) has the min capacity of any //s-t// cut in //G//.
+   (7.) Given a flow f of max value, we can compute an s-t cut of min capaity in O(m) time.
+   In every flow network, the max value of an s-t flow is equal to the min capacity of an s-t cut.
+For interesting, I found this section a 7.
+======7.5 - Bipartite Matching Problem ======
+**The Problem**
+We want to find a matching in //G// of largest possible size.
+**Designing the alg**
+The graph defining a matching problem is undirected, but we can make it work.
+Beginning with a graph //G//, we construct a flow network //G'//. First we direct all edges in //G// from //X// to //Y//. We then add a node //s// and an edge (//s,x//) from //s// to each node in //X//. We add a node //t// and an edge (//y,t//) from each node in //Y// to //t//. Finally, we give each edge in //G'// a capacity of one. Then we compute a max //s-t// flow in this network //G'//.
+**analyzing the alg**
+Here are three simple facts about the set //M'//.
+  * //M'// contains //k// edges.
+  * Each node in //X// is the tail of at most one edge in //M'//.
+  * Each node in //Y// is the head of at most one edge in //M'//.
+  The size of the maximum matching in G is equal to teh value of the max flow in G';
+  and the edges in such a matching in G are the edges that carry flow from X to Y in G'.
+The FF alg can be used to find a max matching in a bipartite graph in //O(mn)// time.
+I give this section an 8.
+======7.7 - Extensions to the Max-Flow Problem ======
+**Circulations with Demands**
+Suppose there is now a set //S// of sources generating flow and a set //t// of sinks. Instead of maximizing the flow values, we will consdier a problem where sources have fixed supply values and sinks have fixed demand values. given a flow network with capacities on the edges, each node //v// has a demand //dv//. If //dv// > 0, the node is a sink. If //dv// < 0, it is a source. //S// denotes the nodes with negative; //T// is the set of nodes with positive demands.
+In this setting we say that a circulation with demands {//dv//} is a function //f// satisfies the capacity and demand conditions.
+So now we just have a feasibility problem.
+  (7.49) If there exists a feasible circulation with demands {dv}, then Σdv = 0.
+See p 382 for proof of:
+There is a feasible circulation with demands {//dv//} in //G// iff the max //s*-t*// flow in //G'// has value //D//. If all capacities and demands in //G// are integers and there is a feasible circulation, then there is a feasible circulation that is integer-valued.
+**Circulations with Demands and Lower Bounds**
+Consider a flow network with a capacity //ce// and a lwoer bound //le// on each edge //e//.
+We simply reduce this problem to the one above. See p383 for proof that
+There is a feasible circulation in //G// iff there is a feasible circulation in //G'//. If all demands, capacities and lower bounds in //G// are integers and there is a feasible circulation, then there is a feasible circulation that is integer-valued.
+This section wasn't very interesting for me, so only a 6.