Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
courses:cs211:winter2014:journals:maggie:home [2014/03/25 20:53] – [6.3 Segmented Least Squares: Multi-way Choices] weatherlym | courses:cs211:winter2014:journals:maggie:home [2014/04/01 23:11] (current) – [7.6 Disjoint Paths in Directed and Undirected Graphs] weatherlym | ||
---|---|---|---|
Line 390: | Line 390: | ||
* * for each segment, the error value of the optimal line through that segment | * * for each segment, the error value of the optimal line through that segment | ||
* our goal is to find a partition of minimum penalty | * our goal is to find a partition of minimum penalty | ||
- | | + | |
+ | | ||
+ | * If the last segment fo the optimal partition is pi,...,pn, then the value of the optimal solution is OPT(n) = ein + C + OPT(i-1) | ||
+ | * For the subproblem on the points p1,...,pj, OPT(j) = min from i = 1 to j (eij + C + OPT(i-1)), and the segment pi,...,pj is used as an optimum solution for the subproblem if and only if the minimum is obtained using index i | ||
+ | |||
+ | Segmented-Least-Squares(n) | ||
+ | Array M[0...n] | ||
+ | Set M[0] = 0 | ||
+ | For all pairs i <= j | ||
+ | Compute the least squares error eij for the segment pi,...pj | ||
+ | For j = 1,...n | ||
+ | Use the recurrence OPT(j) = min from i = 1 to j (eij + C + OPT(i-1)) to compute M[j] | ||
+ | | ||
+ | |||
+ | FindSegments(j) | ||
+ | If j = 0 | ||
+ | output nothing | ||
+ | | ||
+ | Find an i that minimizes eij + C + M[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. | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
====== 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, | ||
+ | Subset-Sum(n, | ||
+ | Array M[0...n, 0....W] | ||
+ | | ||
+ | For i = 1,..n | ||
+ | For w = 0,...,W | ||
+ | Use the recurrence If w < wi then OPT(i, w) = OPT(i-1, w), otherwise | ||
+ | | ||
+ | | ||
+ | |||
+ | * 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, | ||
+ | * Given a table M of the optimal values of the subproblems, | ||
+ | ====== 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, | ||
+ | * We'll refer to the traffic as flow - an abstract entity | ||
+ | * 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 " | ||
+ | * (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). | ||
+ | * 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: | ||
+ | * 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. | ||