Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision
Previous revision
courses:cs211:winter2014:journals:maggie:home [2014/03/25 21:00] – [6.3 Segmented Least Squares: Multi-way Choices] weatherlymcourses:cs211:winter2014:journals:maggie:home [2014/04/01 23:11] (current) – [7.6 Disjoint Paths in Directed and Undirected Graphs] weatherlym
Line 411: Line 411:
           Output the segment {pi,...,pj} and the result of Find-Segments(i-1)           Output the segment {pi,...,pj} and the result of Find-Segments(i-1)
  
 +  * Analyzing the Runtime - first we need to compute the values of all the least-squares errors eij, and to perform this there are O(n^2) pairs (i,j) for which this computation is needed and for each pair we can use the formula given at the begining of the section in O(n) time, giving us O(n^3) for computing the eij error values.  Following this the algorithm has n iterations, and for each j we need to determine the minimum in the recurrence which takes time O(n), giving a running time of O(n^2) once all the eij values have been determined 
  
  
Line 420: Line 420:
  
 ====== 6.4 Subset Sums and Knapsacks: Adding a Variable ====== ====== 6.4 Subset Sums and Knapsacks: Adding a Variable ======
 +  * in this scheduling problem, we have a single machine that can process jobs and a set of requests, we are only able to use this resource for the period between time 0 and time W, for some number W,
 +  * for the knapsack problem, where each request i has both a value vi, and a weight wi, the goal in this problem is to select a subset of maximum total value, subject to the restriction that its total weight not exceed W
 +  * We will use OPT(i, w) to denote the value of the optimal solution using a subset of the items {1,...,i} with maximum allowed weight w, that is OPT(i, w) = maximum over subsets S of {1, ..., i} that satisfy the Summation of j in S where wj <= w
 +  * If n is not in the optimum solution, then OPT(n, W) = OPT(n-1, W), since we can simply ignore item n
 +  * If n is in the optimum solution, then OPT(n, W) = wn + OPT(n-1, W-wn) wince we now seek to use the remaining capacity of W - wn in an optimal way across items 1, 2, ..., n-1
 +  * If w < wi then OPT(i, w) = OPT(i-1, w), otherwise OPT(i, w) = max(OPT(i-1, w), wi + OPT(i-1, w-wi))
  
 +Subset-Sum(n, W)
 +     Array M[0...n, 0....W]
 +     Initialize M[0,w] = 0 for each w = 0,1,...W
 +     For i = 1,..n
 +          For w = 0,...,W
 +               Use the recurrence If w < wi then OPT(i, w) = OPT(i-1, w), otherwise 
 +               OPT(i, w) = max(OPT(i-1, w), wi + OPT(i-1, w-wi)) to compute M[i,w]
 +     Return M[n, W]
 +     
 +  * for the algorithm we've just designed, we  need a two-dimensional table, reflecting the two-dimensional array of subproblems that is being built up
 +  * The Subset-Sum(n, W) algorithm correctly coputes the optimal value of the problem, and runs in O(nW) time
 +  * Given a table M of the optimal values of the subproblems, the optimal set S can be found in O(n) time
  
  
 +====== 7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm ======
 +  * Consider a highway system in which the edges are highways and the nodes are interchanges, network models of this type have several ingredients: capacities on the edges indicating how much they can carry; source nodes in the graph which generate traffic; and sink nodes in the graph which absorb traffic as it arrives, and the traffic itself which is transmitted across the edges
 +  * We'll refer to the traffic as flow - an abstract entity  that is generated at source nodes, transmitted across edges, and absorbed at sink nodes
 +  * flow network is a directed graph G = (V, E) where each edge e is a capacity, which is a nonnegative number denoted ce, there is a single source s in V, and a single sink t in V
 +  * we will say that an s-t flow is a function f that maps each edge e to a nonnegative real number where the value f(e) represents the amount of flow carried by edge e
 +  * For a flow f, each e in E, we have 0 <= f(e) <=ce, and for each node v other than s and t, we have the sum for all edges e into v, f(e) equals the sum of all edges e out of v f(e)
 +  * Given a flow network, the goal is to arrange the traffic so as to make as efficient use as possible of the available capacity
 +  * 
 +====== 7.2 Maximum Flows and Minimum Cuts in a Network ======
 +  * we say that an s-t cut is a partition (A, B) of the vertex set V so that s is in A and t is in B
 +  * the capacity of a cut (A, B), which we will denote c(A, B) is simply the sum of the capacities of all edges out of A
 +  * cuts provide very natural upper bounds on the values of flows
 +  * Let f be any s-t flow, and (A, B) any s-t cut, then v(f) = f out (A) - f in (A), this statement says that by watching the amount of flow f sends across a cut, we can exactly measure the flow value, it is the total amount that leaves A, minus the amount that "swirls back" into A
 +  * (7.8) Let f be any s-t flow, and (A, B) any s-t cut, then v(f) <= c(A, B)
 +  * Let f bar denote the flow that is returned by the Ford-Fulkerson Algorithm, we want to show that f bar has the maximum possible value of any flow in G
 +  * 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 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
 +  * The flow f bar returned by the Ford-Fulkerson Algorithm is a maximum flow
 +  * Given a flow f of maximum value, we can compute an s-t cut of minimum capacity in O(m) time
 +  * The point is that f must be a maximum s-t flow for if there were a flow f' of greater value, the value of f' would exceed the capacity of (A, B), and this would contradict (7.8).  Similarly, it follows that (A, B) is a minimum cut - no other cut can have a smaller capacity, for if there were a cut (A', B') of smaller capacity, it would be less than the value of f, and this again would contradict (7.8), so this gives us the Max-Flow Min-Cut Theorem - In every flow network, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut
 +  * If all capacities in the flow network are integers, then there is a maximum flow f for which every flow value f(e) is an integer
  
 +====== 7.5 A First Application: The Bipartite Matching Problem ======
 +  * Beginning with the graph G in an instance of the Bipartite Matching, we construct a flow network G', first we direct al 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 1, we now compute a maximum s-t flow in this network G'
 +  * The size of the maximum matching in G is equal to the value of the maximum 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 Ford-Fulkerson Algorithm can be used to find a maximum matching in a bipartite graph in O(mn) time, where m is the number of edges
 +  * We can decide if the graph G has a perfect matching by checking if the maximum flow in a related graph G' has value at least n, by the Max-Flow Min-Cut theorem there will be an s-t cut of capacity less than n if the maximum -flow value in G' has value less than n
 +  * If there are nodes x1 and x2 in X that have only one incident edge each, and the other end of each edge is the same node y, then clearly the graph has no perfect matching
 +  * Assume that the bipartite graph G = (V, E) has two sides X and Y st the size of X is equal to the size of Y.  Then the graph G either has a perfect matching or there is a subset A of X st the size of Gamm(A) < the size of A where Gamm(A) is a subset of Y and denotes the set of all nodes that ar adjacent to nodes in A.  A perfect matching can be found in O(mn) time
  
 +====== 7.6 Disjoint Paths in Directed and Undirected Graphs ======
 +  * We say that a set of paths is edge-disjoint if no two paths share an edge,
 +  * Given a directed graph G = (V, E) with two distinguished nodes s, t in V, the Directed Edge-Disjoint Paths Problem is to find the maximum number of edge-disjoint s-t paths in G
 +  * The Undirected Edge-Disjoint Paths Problem is to find the maximum number of edge-disjoint s-t paths in an undirected graph G
 +  * Both directed and the undirected versions of the problem can be solved using flows, starting with the directed problem, given the graph G = (V, E) we define a flow network in which s and t are the source and sink, and with capacity of 1 on each edge, suppose there are k edge-disjoint s-t paths, we can make each of these carry one unit of flow.  If there are k edge-disjoint paths in a directed graph G from s to t, then the value of the maximum s-t flow in G is at least k
 +  * If f is a 0-1 valued flow of value v, then the set of edges with flow value f(e) = 1 contains a set of v edge-disjoint paths
 +  * There are k edge-disjoint paths in a directed graph G from s to t if and only if het value of the maximum value of an s-t flow in G is at least k
 +  * The Ford-Fulkerson Algorithm can be used to find a maximum set of edge-disjoint s-t paths in a directed graph G in O(mn) time
 +  * In every directed graph with nodes s and t, the maximum number of edge-disjoint s-t paths is equal to the number of edges whose removal separates s from t
 +  * There are k edge-disjoint paths in an undirected graph G from s to to if and only if the maximum value of an s-t flow in the directed version G' of G is at least k.  The Ford-Fulkerson Algorithm can be used to find a maximum set of disjoint s-t paths in an undirected graph G in O(mn) time
 +  * In every undirected graph with nodes s and t, the maximum umber of edge-disjoint s-t paths is equal to the minimum number of edges whose removal separates s from t.  
  
  
  
courses/cs211/winter2014/journals/maggie/home.1395781216.txt.gz · Last modified: 2014/03/25 21:00 by weatherlym
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0