Differences

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

--- courses:cs211:winter2014:journals:maggie:home [2014/03/25 01:19] – [6.2 Principles of Dynamic Programming: Memoization or Iteration over Subproblems] weatherlym
+++ courses:cs211:winter2014:journals:maggie:home [2014/04/01 23:11] (current) – [7.6 Disjoint Paths in Directed and Undirected Graphs] weatherlym
@@ Line 372: / Line 372: @@
     For j from 1 to n
         M[j] = max(vj + M[p(j)], M[j-1])
-ds
   * this algorithm write OPT(j) in array entry M[j], we can pass the filled-in array M to Find-Solution to get an optimal solution in addition to the value, finally running time of Iterative-Compute-Opt is clearly O(n) since it explicitly runs for n iterations and spends constant time on each
-  * this provides a second efficient algorithm to solve the Weighted Interval Scheduling Problem,
+  * this provides a second efficient algorithm to solve the Weighted Interval Scheduling Problem
+A Basic Outline of Dynamic Programming
+  * iterative building up of subproblems, to set about developing an algorithm based on dynamic programming, one needs a collection of subproblems derived from the original problem that satisfies a few basic propterties
+  - There are only a polynomial number of subproblems
+  - The solution to the original problem can be easily computed from teh solutions to the subproblems
+  - there is a natural ordering on subproblems from smallest to largest, together with an easy-to-compute recurrence that allows one to determien the solution to a subproblem from the solutions to some number of smaller subproblems
 ====== 6.3 Segmented Least Squares: Multi-way Choices ======
+  * multi-way choices - at each step, we have a polynomial number of possibilities to consider for the structure of the optimal solution
+  * plotted on a two-dimensional set of axes, one tries to pass a line of best fit through the data, find the line with the minimum error y = ax + b where a and b are defined on page 262
+  * given a set of points where each x value is unique, we must partition P into some number of segments where P is the set of points, each segment is a subset of P that represents a contiguous set of x-coordinates, for each segment S in our partition of P we compute the line minimizing the error with respect to the points in S
+  * the penalty of a partition is defined by the sum of the following terms
+  *   * the number of segments into which we partition P, times a fixed given multiplier c > 0
+  *   * for each segment, the error value of the optimal line through that segment
+  * our goal is to find a partition of minimum penalty
+  * let OPT(i) denote the optimum solution for the points p1,...,pn and let eij denote the minimum error of any line with repect to pi, pi+1,...,pj
+  * 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]
+     Return M[n]
+FindSegments(j)
+     If j = 0
+          output nothing
+     Else
+          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.  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
 ====== 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.