Algorithm to match preferred partners into groups of three

Question

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!

Answer 1

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.

Answer 2

This is different from an extension of the stable marriage problem, since as I understand the OP's question, the people in each group do not have an ordered list of who they want to work with from most to least; it's a binary relationship (willing/not willing).

This can be formulated as an integer programming problem that can be solved quite quickly. I give the mathematical formulation of the problem below; you can use a package like glpk or AMPL/CPLEX to process the data.

Define the following matrices:

M1 = |A| x |B| matrix, where

M1(a,b) = 1 if a (given member of A) is willing to work with b (given member of B), and 0 otherwise

M2 = |A| x |C| matrix, where M2(a,c) = 1 if a (given member of A) is willing to work with c (given member of C), and 0 otherwise

M2 = |B| x |C| matrix, where

M3(b,c) = 1 if b (given member of B) is willing to work with c (given member of C), and 0 otherwise

Now define a new matrix we will use for our maximization:

X = |A| x |B| x |C| matrix, where

X(a,b,c) = 1 if we make a, b, and c work together.

Now, define our objective function:

//Maximize the number of groups

maximize Sum[(all a, all b, all c) X(a,b,c)]

subject to the following constraints:

//To ensure that nobody gets placed in two groups

For all values of a: Sum[(all j, k) X(a, j, k)] <= 1

For all values of b: Sum[(all i, k) X(i, b, k)] <= 1

For all values of c: Sum[(all i, j) X(i, j, c)] <= 1

//To ensure that all groups are composed of compatible individuals

For all a,b,c: X(a,b,c) <= M1(a,b)/3 + M2(a,c)/3 + M3(b,c)/3

Answer 3

To start with, you can eliminate any facts where the two parties have disjoint lists of who they will work with in the third group. Then start a brute force, depth first search, always picking from least popular to most popular.

Alternatively, equivalent to the above elimination, form a list of all possible trios and work from that instead.

Answer 4

Just a quick note to this problem. First, it is not an example of the stable marriage problem, nor in fact an extension of it (i.e. the 3D stable matching problem). Regardless though, it is a 3D matching problem which known to be NP-hard (see Garey and Johnson). To solve such a problem in a reasonable way, it is likely that you will need to use some form of constraint, integer, or linear programming (others methods exist). Something that might be of use is the new Microsoft Solver Foundation, so check it out.