I have a practical application where I need to map elements from one set (A) to another (B).
- Sets A and B can both have arbitrary numbers of elements
- Elements from A and B need to be paired up so that every element can only be used once.
- Elements can be left unpaired as well.
- A similarity matrix can be calculated: how well any element from A maps to any element from B.
- The goal is to find a mapping that maximizes the sum of these similarity scores.
Brute-forcing all the options gives factorial complexity which gets out of hand fast. However, for many examples a simple greedy approach seems to work fine - iteratively add the edge which has the maximum score in the similarity matrix, making sure that the restrictions still apply.
Is there any guarantee that this greedy approach will give me the maximized result? I haven't been able to come up with a good counter-example but that doesn't mean they don't exist.