Say your client works with travelers (T), and each of them has a list of wished destinations (D) for the week-end. We’d like to associate each traveler with one single destination, each accepting only one person, but in an optimized way (that is in short, having as many associations as possible).
For instance, say Bob wants to visit both Paris and Madrid, and Alice wants to go to Paris. We would set Bob to Madrid, and Alice to Paris (2 matches), because if we’d placed Bob on Paris, we could not create any further match with Alice, and we’d end up with only 1 match.
Is there any algorithm which could tell us, in less than a second, what is the best combination, when we have millions of possible travelers and destinations? Yes, and it would use the min-cut/max-flow theorem.
Here are two lessons on it. Note that it may be used for much more cases than imagined.
The first is done by Polytechnique, and is pretty good (French).
This one is by Princeton, with code examples, less clean, but useful too.
Top comments (0)