Differences

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

--- courses:cs211:winter2014:journals:cory:home [2014/03/22 01:49] – walkerc
+++ courses:cs211:winter2014:journals:cory:home [2014/03/31 21:51] (current) – walkerc
@@ Line 113: / Line 113: @@
 ===== 6.4 Summary =====
 In the subset sums and knapsacks problem, the "obvious" set of subproblems turns out to not be enough, and we end up creating a richer collection of subproblems. This is done by adding a new variable to the recurrence underlying the dynamic program. Here we have a single machine that can process jobs between the times of 0 and W for some W. Our goal is to process jobs so as to keep the machine as busy as possible up to the W "cut-off." Given n items that each have a nonnegative weight, and a bound W, we want to select a subset S of the items so that the sum of each of the items' weights is less than the W cut-off, while the sum of all of their weights is as large as possible. This is called the Subset Sum Problem, which is a natural special case of the Knapsack Problem where each request i has both a value and a weight. Dynamic programming can be used to solve this problem. The Subset-Sum(n, W) Algorithm correctly computes 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. The Knapsack Problem can be solved in O(nW) time. Question: Is there another algorithm (not using dynamic programming) that can find an equally efficient solution/running time? Interest: 7/10
+===== 7.1 Summary =====
+Graphs can often be used to model transportation networks, whose edges carry "traffic" and whose nodes act as "switches" passing traffic between different edges. Network models have: capacities on the edges, source nodes which generate traffic, sink (destination) nodes, and the traffic itself (or flow) which is transmitted across the edges. To find a maximum flow in a network, with the smallest bottleneck, we must answer the Maximum-Flow Problem with a combination of greedy and dynamic programming. We can push forward on edges with leftover capacity and backward on edges that are already carrying flow to change its direction. A residual graph provides a systematic way to search for forward-backward operations like this.The algorithm that answers this is known as the Ford-Fulkerson Algorithm, which runs in O(mC) time. Question: Which parts of this are dynamic programming, and which are greedy? Interest: 6/10
+===== 7.2 Summary =====
+This section is about the analysis of the Ford-Fulkerson Algorithm, and how it provides insight into the Maximum-Flow Problem. Here we see and prove that the Ford-Fulkerson Algorithm has the maximum possible value of any flow in G. By watching the amount of flow f (any s-t flow) sends across a cut, we can measure the flow value. Let f be any s-t flow and (A, B) any s-t cut. Then v(f) ≤ c(A, B). If f is an s-t-flow such that there is no s-t path in the residual graph G_f, 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. Given a flow f of maximum value, we can compute an s-t cut of minimum capacity in O(m) time. 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. Question: Because this algorithm could potentially run forever, is it really always efficient? Interest: 6/10
+===== 7.5 Summary =====
+One of the main goals of the Maximum-Flow Problem is to be able to solve the Bipartite Matching Problem. A bipartite graph G=(V, E) is an undirected graph whose node set can be partitioned so that every edge has one end in X and the other in Y. A matching M in G is a subset of the edges so that each node appears in at most one edge in M. The Bipartite Matching Problem involves finding a matching in G of largest possible size. 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. Assume that the bipartite graph G = (V, E) has two sides X and Y such that |X| = |Y|. Then the graph G either has a perfect matching or there is a subset A⊆X such that |Γ(A)| < |A|. A perfect matching or an appropriate subset A can be found in O(mn) time. Question: What real world applications do bipartite graphs have? Interest: 4/10
+===== 7.7 Summary =====
+In the Maximum-Flow Problem, we had only a single source s and a single sink t. Now we can have a set S of sources and a set T of sinks. Instead of maximizing the flow value, we will have sources that have fixed supply values and sinks with fixed demand values, and we want to ship flow from nodes with supply to those with demands. There is a feasible circulation with demands {d_v} in G if and only if the maximum 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. There is a feasible circulation in G if and only if 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. Question: Is this algorithm just a slightly tweaked version of the Ford-Fulkerson Algorithm? Interest: 6/10