2 ms·
At work, we had a problem that's similar to the stable marriage problem. We ended up finding another combinatorial optimization problem called the "assignment p
by konaraddi 6y ago
At work, we had a problem that's similar to the stable marriage problem. We ended up finding another combinatorial optimization problem called the "assignment problem" [0] that fit more closely with our problem. Here's a brief summary of the assignment problem:
Suppose you had people in two groups A and B where each individual in group A wants to pair up with an individual in group B and visa versa. If you can assign a "compatibility score" to each possible pair, then the goal is to find the set of pairs, where a pair consists of an individual from A and an individual from B, that maximizes the sum of the compatibility scores. In other words, the assignment problem is about finding the best 1:1 mapping between groups A and B when given a compatibility score for every possible pair between the groups of individuals.
[0] https://en.wikipedia.org/wiki/Assignment_problem https://en.wikipedia.org/wiki/Assignment_problem
- viklove 6y agoThis isn't how it works in the real world at all, though. People want to optimize for their own pair, with no regard for "maximizing the sum of all compatibility scores." In other words, I don't care about anyone else's marriage, I only want me and my partner to be as happy as possible.
- konaraddi 6y agoAbsolutely! I agree. To be clear, I brought up the linear sum assignment problem because it’s relevant, I liked reading about it, and perhaps someone else here would like to read about it too. At work, we applied the linear sum assignment problem when comparing results from a tracking algorithm to the truth data.