Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2012:journals:lee:home [2012/03/25 19:59] – [Section 6.4: Subset Sums and Knapsacks: Adding a Variable] davisl | courses:cs211:winter2012:journals:lee:home [2012/04/02 21:15] (current) – [Section 7.7: Extensions to the Maximum-Flow Problem] davisl | ||
|---|---|---|---|
| Line 109: | Line 109: | ||
| ==== Section 6.4: Subset Sums and Knapsacks: Adding a Variable ==== | ==== Section 6.4: Subset Sums and Knapsacks: Adding a Variable ==== | ||
| - | In section 6.4, the authors discuss Subset sums and a variation of the Subset Sum problem called the Knapsack problem. The goal of the Subset Sums is to schedule as many jobs, with a duration w_{i}, to a machine without going over the maximum time W. The Knapsack problem is a little more complex since the goal is to find the subset of items with the highest possible value, but whose combined weight is less than the maximum weight W. In contrast to the previous section, the subproblems are binary decisions, either the job or item is in the optimal solution or it is not. The subproblem and algorithm can be found on page 269. The runtime of the algorithm is O(nW). | + | In section 6.4, the authors discuss Subset sums and a variation of the Subset Sum problem called the Knapsack problem. The goal of the Subset Sums is to schedule as many jobs, with a duration w_{i}, to a machine without going over the maximum time W. The Knapsack problem is a little more complex since the goal is to find the subset of items with the highest possible value, but whose combined weight is less than the maximum weight W. In contrast to the previous section, the subproblems are binary decisions, either the job or item is in the optimal solution or it is not. The subproblem and algorithm can be found on page 269. The runtime of the algorithm is O(nW). |
| + | ===== Chapter 7: Network Flow ===== | ||
| + | Is a class of problem, where each edge in a directed graph has flow and each node can receive and send " | ||
| + | ==== Section 7.1: The Maximum-Flow Problem and the Ford-Fulkerson Algorithm ==== | ||
| + | The Maximum-Flow Problem is concerned with finding the maximum amount of flow that is possible on a given directed graph so that all edges are used efficiently. The maximum-flow of any given graph is actually the minimum capacity of some partition or " | ||
| + | |||
| + | ==== Section 7.2: Maximum Flows and Minimum Cuts in a Network ==== | ||
| + | In section 7.2, the authors further analyze the Ford-Fulkerson algorithm. They conclude that the algorithm is guaranteed to return the maximum flow, which is based on the minimum cut. This is due to the property that the value of some flow f, v(f) is equal to the difference of the number of edges leaving and entering a cut. Therefore, v(f) is guaranteed to be bounded by the capacity of some cut. | ||
| + | |||
| + | ==== Section 7.5: A First Application: | ||
| + | The Ford-Fulkerson algorithm not only solves the Maximum-Flow Problem but also the Bipartite Matching Problem. The Bipartite Matching Problem is determining what is the largest subset of edges of some graph such that each node appears at most once in a particular matching. The minimum cut returned from the Ford-Fulkerson Algorithm is the largest matching in a given graph. The runtime of the algorithm in solving the Bipartite Matching problem is O(mn) and the explanation is on page 370. To determine if a particular matching is perfect, the size of the subset of some nodes |A|, must be less than the size of the rest of the nodes. The proof is on page 372. | ||
| + | |||
| + | ==== Section 7.7: Extensions to the Maximum-Flow Problem === | ||
| + | In section 7.7, the authors discuss extensions to the Maximum-Flow problem. In the one of these extensions, the graph is similar to the one constructed in the Bipartite Matching Problem with a source node connecting a set of nodes labelled as suppliers which are connected to consumers. The set of consumers are in turn connected to a sink node. Each edge has a flow and capacity | ||
