2
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ Thanks, I had an intuition there would be an algorithm for that but wasn't able to find it. $\endgroup$ – Marek Feb 18 '12 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.