2
$\begingroup$

Let's say there are two lists of objects, list1 and list2, and that there is a function that can generate the "distance" between an object in list1 and an object in list2. What I would like to do is create a list of pairs of objects from each list such that the sum of all the distances of each of the pairs is minimal.

The only method that has occurred to me so far is just a brute force solution of creating a matrix of all the distances between list1 and list2 and then examining the sums of the distances of all possible combinations. Obviously, that approach is rather unappealing. I'm sure that many people have come across a similar problem before but I've been having a hard time phrasing my question in such a way that Google can help me out. Anybody have any ideas?

asked Aug 12, 2015 at 19:55
$\endgroup$
1
  • $\begingroup$ Maximal/complete matching in a weighed bipartite graph is what I'd be searching for. $\endgroup$ Commented Aug 12, 2015 at 21:14

1 Answer 1

2
$\begingroup$

This seems to be a classical example of bipartite weighted maximum matching, for which there are efficient algorithms (you'll have to convert your minimization objective to a maximization one).

answered Aug 12, 2015 at 20:22
$\endgroup$
1
  • $\begingroup$ Yes, thank you, that's exactly what this is. Wikipedia has a good run-down of one of the potential algorithm here. $\endgroup$ Commented Aug 12, 2015 at 20:38

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.