Menu
What's a good algorithm to solve this problem?
I have three groups of people - group A, group B, and group C. There are the same number of people in each group. They each have a list of people in the other groups that they're willing to work with. I want to group all these people together in groups of 3 (one from A, one from B, and one from C) such that everyone in a group wants to work with the other people in their group.
How can I find these groups in a fast way? If there's no way to make everyone happy, then the algorithm should first make as many groups have three people who want to work with each other, and then make as many people in the other groups happy.
One final point: people agree on who they want to work with (if person x wants to work with person y, then y also wants to work with x). If you could also give a big-O of the running time of your algorithm, that'd be great!
974
BM25 [5] is the Best Matching ranking algorithm that ranks the documents according to its relevance to the given search query.
Following is Gale–Shapley algorithm to find a stable matching: The idea is to iterate through all free men while there is any free man available. Every free man goes to all women in his preference list according to the order. For every woman he goes to, he checks if the woman is free, if yes, they both become engaged.
Single keyword pattern matching algorithms are used to find all occurrences of a specific keyword in a given input. Due to the size of the keyword set is one these types of algorithms will be very limited in modern Network Security Systems.
To evaluate your matching algorithm, you may manually identify some landmarks (keypoint) in the first image (X1) and their correspondence in the second image(Xac). Given the landmarks of the first image(X1), use your matching algorithm to find their correspondence in the second image (Xm).
This is like the stable marriage problem, but with 3 parties instead of two.
Have a look at efficient solutions for former problem (bi-partite graph matching) and adapt them to your needs.
http://en.wikipedia.org/wiki/Stable_marriage_problem
One adaptation could be to first build working pairs from groups A and B only. Then these pairs have to be paired with a worker from group C each. Let the pairs only prefer workers which both members of the pair agree on (given their lists). Note that this will only give a local optimum.
An optimal solution to k-partite matching is NP-hard to find:
http://www.math.tau.ac.il/~safra/PapersAndTalks/k-DM.ps
See this paper for a non-optimal solution to the k-partite matching problem:
http://books.google.com/books?id=wqs31L1MF4IC&pg=PA309&lpg=PA309&dq=k-partite+matching&source=bl&ots=kgBuvi7ym_&sig=j3Y-nyo51y8qp0-HwToyUlkao4A&hl=de&sa=X&oi=book_result&resnum=1&ct=result
I'm sure you can find others on Google yourself now that you know the terms to search for. I don't know if there is an efficient algorithm giving the optimal solution for k=3.
64
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
