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

Question

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.

Answer 1

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$.

The problem you are solving is called the assignment problem and it's well studied. It can be solved in polynomial time by the Hungarian algorithm, for example.