# Finding an injective mapping between two sets that maximizes a similarity function

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.

• Not research-level questions are off-topic on this site. Feb 18 '12 at 14:08
• It's a question about combinatorial optimization algorithms. Where would be a better place? Feb 18 '12 at 14:42
• It would be on-topic on the proposed computer science site. Feb 18 '12 at 15:34
• While what @DmytroKorduban says is technically correct, this questions falls into the realm of 'modelling' questions, that we do encourage on this site. Feb 18 '12 at 16:15
• @SureshVenkat That should be stated more explicitly in FAQ or wheresoever. I was sure it's off-topic even after reading the meta discussion. Feb 18 '12 at 16:45

The simplest counter-example is something like an "anti-multiplication table": for $A=B=\left\{1,2,\ldots,n\right\}$ let's define the cost function as $cost(a, b) = n^2 - ab$. The greedy algorithm will fail for $n \ge 2$.