Pair matching algorithm

Question

I am working on a rails app that requires constantly matching users together. Basically I need an algorithm that will take as its input a list of users and return a list of pairs that best match. Users are considered good matches by criteria such has more interests in common or distance between them. In general I need to be able to tweak what is considered a "good match" but I just need a direction to head in for the algorithm that will take a set of users and return a set of pairs.

If it helps, I have a method in the user model that take as a param another user and return s a score of how good a match it is. I need help putting that to use in mass matching.

I plan on having users enter into a table and then a cron job running through the list every so often to find the best pair matches between everyone. Anyone have any ideas?

Thanks so much!

Answer 1

Jack Edmonds' algorithm finds a maximum weight matching in a general (non-bipartite) graph.

Vladimir Kolmogorov has a paper and an implementation in C++.

---

Edited to add: If you don't mind about not getting the best matching, and you want something that's easy to compute, then why not use the simple greedy algorithm? At each stage, pair off the two users with the highest scoring match. Then pair off the two users with the highest scoring match among the remaining users, and so on.