Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2018:journals:melkersonr:chapter7 [2018/04/03 03:41] – [Section 7.5] melkersonr | courses:cs211:winter2018:journals:melkersonr:chapter7 [2018/04/03 03:42] (current) – [Section 7.7] melkersonr |
|---|
| ===== Section 7.7 ===== | ===== Section 7.7 ===== |
| |
| * **Summary & Motivations:** Section 7.7 is Extensions to the Maximum-Flow Problem. This subsection deals with extensions to the Max-Flow problem, as the title suggests. This sentence sums up the power of the Max-Flow problem pretty well: "The power of the Maximum-Flow Problem lies in the fact that many problems with a nontrivial combinatorial search component can be solved in polynomial time because they can be reduced to the problem of finding a maximum flow or a minimum cut in a directed graph" (p 379). We explore two related problems here: Circulations with Demands, first without and then with Lower Bounds. Here we allow more than one source and more than one sink. Now instead of deciding which source or sink to use, we'll image that sources have supplies and sinks have demands, of flow. We have the same capacity condition for this problem, but there is no conservation condition anymore. It is more or less replaced by the demand condition: for each node in V, the flow into v minus the flow out of v is equal to v's demand. Further, this problem is no longer about maximization. Rather, it's about feasibility. We want to know if it's possible to satisfy all demands. The only difference between no lower bounds and having lower bounds is that when there are lower bounds on the edges it means that the minimum flow for that edge is its lower bound, not zero. | * **Summary & Motivations:** Section 7.7 is Extensions to the Maximum-Flow Problem. This subsection deals with extensions to the Max-Flow problem, as the title suggests. This sentence sums up the power of the Max-Flow problem pretty well: "The power of the Maximum-Flow Problem...lies in the fact that many problems with a nontrivial combinatorial search component can be solved in polynomial time because they can be reduced to the problem of finding a maximum flow or a minimum cut in a directed graph" (p 379). We explore two related problems here: Circulations with Demands, first without and then with Lower Bounds. Here we allow more than one source and more than one sink. Now instead of deciding which source or sink to use, we'll image that sources have supplies and sinks have demands, of flow. We have the same capacity condition as before for this problem, but there is no conservation condition anymore. It is more or less replaced by the demand condition: for each node in V, the flow into v minus the flow out of v is equal to v's demand. Further, this problem is no longer about maximization. Rather, it's about feasibility. We want to know if it's possible to satisfy all demands. The only difference between no lower bounds and having lower bounds is that when there are lower bounds on the edges it means that the minimum flow for that edge is its lower bound, not zero. |
| * **About the Algorithms:** We solve the problem that has no lower bound by adding a "super source" that supplies everything in S and a "super sink" that siphons from everything in T. Then the problem reduces to the Max-Flow algorithm, and the runtime is O(Cm). We solve the problem //with// lower bounds by reducing it to a problem with no lower bounds. We simply push flow down edges at a value equal to their lower bound and adjust the upper bound on that edge and the demands at its two ends accordingly. | * **About the Algorithms:** We solve the problem that has no lower bound by adding a "super source" that supplies everything in S and a "super sink" that siphons from everything in T. Then the problem reduces to the Max-Flow algorithm, and the runtime is O(Cm). We solve the problem //with// lower bounds by reducing it to a problem with no lower bounds. We simply push flow down edges at a value equal to their lower bound and adjust the upper bound on that edge and the demands at its two ends accordingly. |
| * **My Questions:** What examples are there for when lower bounds would occur? The book didn't give any. | * **My Questions:** What examples are there for when lower bounds would occur? The book didn't give any. |
| * **Second Time Around:** Technically, this //was// the “first time around,” since we did not have class 4/2, so I cannot say that anything made sense the second time I saw it. | * **Second Time Around:** Technically, this //was// the “first time around,” since we did not have class 4/2, so I cannot say that anything made more sense the second time I saw it. |
| * **Note to Self:** Figure 7.14 reminds me of things we did in CSCI 313. | * **Note to Self:** Figure 7.14 reminds me of things we did in CSCI 313. |
| * **Readability:** 8 - pretty straightforward. | * **Readability:** 8 - pretty straightforward. |
| |
