1
$\begingroup$

I have two sets of elements M and N, and a scalar-valued distance/similarity function between one element from M and one from N. The problem is to generate a set of pairs (one item from M and one from N) which minimizes the sum of the distance function.

Caveats

  • Using an existing package in R would be ideal
  • M and/or N may contain "extra" elements that don't have a partner; therefore M and N may be of unequal length
  • We have a starting configuration which is reasonably close

My first thought in addressing this is a monte carlo or genetic algorithm. So perhaps as a solution someone could show how to use an R genetic algorithm package for this problem.

Also see this unanswered question.

Improve this question
$\endgroup$
4
  • $\begingroup$ Some additional constraints are needed, for after all one can achieve a minimum sum of distances by choosing no elements from either set. Do you intend that all elements in the smaller set have pairs? If so, is the pairing supposed to be one-to-one? Is your function a true distance (that is, does it satisfy the reflexive, symmetric, and triangle inequality axioms)? $\endgroup$
    – whuber ♦
    Commented Jun 26, 2014 at 18:02
  • 1
    $\begingroup$ (1) Then function satisfies the reflexive, symmetric, and triangle inequality axioms (2) For starters I would like to require each element from the smaller list to be paired with an element from the larger list. This is an applied rather than theoretical problem; make whatever assumptions we need to get a reasonable set of pairs. $\endgroup$
    – Pete
    Commented Jun 26, 2014 at 18:36
  • $\begingroup$ Also, minimizing the distance function is not the ultimate goal, rather to generate a set of pairs. I thought there might be a way to frame it as a GA problem in R if it was expressed this way. $\endgroup$
    – Pete
    Commented Jun 26, 2014 at 18:56
  • 1
    $\begingroup$ If you have MxN matrix of distances, Hungarian algorithm (or some other linear programming aproach) will get you Q=min(M,N) pairs with absolute minimal the overall sum of within-pair distances. (There is also a modification allowing to request Q<min(M,N), - not very efficient wrt speed, but working. $\endgroup$
    – ttnphns
    Commented Jun 26, 2014 at 21:52

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.