# 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. Commented Feb 18, 2012 at 14:08
• It's a question about combinatorial optimization algorithms. Where would be a better place? Commented Feb 18, 2012 at 14:42
• It would be on-topic on the proposed computer science site. Commented Feb 18, 2012 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. Commented Feb 18, 2012 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. Commented Feb 18, 2012 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$.