Swipe to navigate through the chapters of this book
Please log in to get access to this content
To get access to this content you need the following product:
If you allow them to specify a degree of preference, this turns into the more general min-cost bipartite matching, or the assignment problem. Although a highly useful problem, it’s a bit harder to solve—I’ll get to that later.
In some ways, this problem is similar to the path counting in Chapter 8. The main difference, however, is that in that case we counted all possible paths (such as in Pascal’s Triangle), which would usually entail lots of overlap—otherwise the memoization would be pointless. That overlap is not permitted here.
Actually, the proof I used in the zero-one case was just a simplified version of the proof I use here. There are proofs for Menger’s theorem that don’t rely on the idea of flow as well.
This section is a bit hard and is not essential in order to understand the rest of the book. Feel free to skim it or even skip it entirely. You might want to read the first couple of paragraphs, though, to get a feel for the problem.
This is, of course, pseudopolynomial, so choose your capacities wisely.
Also available online: http://books.google.com/books?id=NvuFAglxaJkC&pg=PA299
Note that the sum here is the in-edge lower bounds minus the out-edge lower bounds—the opposite of how we sum the flows. That’s exactly the point.
- Matchings, Cuts, and Flows
Magnus Lie Hetland
- Sequence number
- Chapter number
- Chapter 10