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

<p>The problem you are solving is called the <a href="http://en.wikipedia.org/wiki/Assignment_problem">assignment problem</a> and it's well studied. It can be solved in polynomial time by the <a href="http://en.wikipedia.org/wiki/Hungarian_algorithm">Hungarian algorithm</a>, for example.</p>

CC BY-SA 3.0
2012-02-18T14:35:05.880Z
Thanks, I had an intuition there would be an algorithm for that but wasn't able to find it.
Marek
CC BY-SA 3.0
2012-02-18T13:53:55.317Z
2012-02-18T14:04:14.290Z
2012-02-18T14:04:14.290Z
Dmytro Korduban
<p>I have a practical application where I need to map elements from one set (A) to another (B).</p>

<ul>
<li>Sets A and B can both have arbitrary numbers of elements</li>
<li>Elements from A and B need to be paired up so that every element can only be used once.</li>
<li>Elements can be left unpaired as well.</li>
<li>A similarity matrix can be calculated: how well any element from A maps to any element from B.</li>
<li>The goal is to find a mapping that maximizes the sum of these similarity scores.</li>
</ul>

<p>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. </p>

<p>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. </p>

CC BY-SA 3.0
2012-02-18T14:08:19.277Z
Not research-level questions are off-topic on this site.
Dmytro Korduban
CC BY-SA 3.0
2012-02-18T14:42:20.967Z
It's a question about combinatorial optimization algorithms. Where would be a better place?
Marek
CC BY-SA 3.0
2012-02-18T15:34:26.907Z
It would be on-topic on the [proposed computer science site](http://area51.stackexchange.com/proposals/35636/computer-science).
Dmytro Korduban
CC BY-SA 3.0
2012-02-18T16:15:53.873Z
While what @DmytroKorduban says is technically correct, this questions falls into the realm of 'modelling' questions, that we *do* encourage on this site.
Suresh Venkat
CC BY-SA 3.0
2012-02-18T16:45:05.277Z
@SureshVenkat That should be stated more explicitly in FAQ or wheresoever. I was sure it's off-topic even after reading the [meta discussion](http://meta.cstheory.stackexchange.com/questions/514/how-to-model-this-questions).
Dmytro Korduban
CC BY-SA 3.0
2012-02-19T23:01:05.630Z
@DmytroKorduban: I agree that the issue is on shaky ground.  If this question did not start with “I have a practical application where,” then it might have been closed as off topic.  So in some sense, it seems that all one has to do to make an arbitrary question on-topic is to claim that there is a practical application behind the question.  (This does not mean that I think that Marek is telling a lie.)
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-21T01:56:36.457Z
There definitely is a practical aspect - in fact, this problem is a small (but important) abstracted part of a computer science research project. However, disregarding the practical aspect, doesn't theoretical computer science very much include algorithms? My question was whether a specific algorithm is guaranteed to be correct, and whether there exists a more efficient algorithm for the problem.
Marek
CC BY-SA 3.0
2012-02-22T09:59:18.810Z
Marek, yes this can be a real theoretical question, but it's not research level and doesn't belong to this site, you can see [FAQ](http://cstheory.stackexchange.com/faq) for more detail.
Saeed
<ds.algorithms>
Finding an injective mapping between two sets that maximizes a similarity function
Marek
# Finding an injective mapping between two sets that maximizes a similarity function

(Asked by: username_0 on 2012-02-18)

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.

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: Not research-level questions are off-topic on this site.  
> **username_0**: It's a question about combinatorial optimization algorithms. Where would be a better place?  
> **username_1**: It would be on-topic on the [proposed computer science site](http://area51.stackexchange.com/proposals/35636/computer-science).  
> **username_2**: While what @DmytroKorduban says is technically correct, this questions falls into the realm of 'modelling' questions, that we *do* encourage on this site.  
> **username_1**: @SureshVenkat That should be stated more explicitly in FAQ or wheresoever. I was sure it's off-topic even after reading the [meta discussion](http://meta.cstheory.stackexchange.com/questions/514/how-to-model-this-questions).  
> **username_3**: @DmytroKorduban: I agree that the issue is on shaky ground.  If this question did not start with “I have a practical application where,” then it might have been closed as off topic.  So in some sense, it seems that all one has to do to make an arbitrary question on-topic is to claim that there is a practical application behind the question.  (This does not mean that I think that Marek is telling a lie.)  
> **username_0**: There definitely is a practical aspect - in fact, this problem is a small (but important) abstracted part of a computer science research project. However, disregarding the practical aspect, doesn't theoretical computer science very much include algorithms? My question was whether a specific algorithm is guaranteed to be correct, and whether there exists a more efficient algorithm for the problem.  
> **username_4**: Marek, yes this can be a real theoretical question, but it's not research level and doesn't belong to this site, you can see [FAQ](http://cstheory.stackexchange.com/faq) for more detail.  

---

## 1 answers

### Answer by username_1 on 2012-02-18. Score: 9 | Accepted answer

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](http://en.wikipedia.org/wiki/Assignment_problem) and it's well studied. It can be solved in polynomial time by the [Hungarian algorithm](http://en.wikipedia.org/wiki/Hungarian_algorithm), for example.

> **Comments:**
> **username_0**: Thanks, I had an intuition there would be an algorithm for that but wasn't able to find it.  

---

