CODEWITHSUNDEEP
algorithmmatching
Cheetah
Cheetah

Reputation: 14379

Some sort of stable matching algorithm needed

Im not even sure this is a stable matching problem.

The problem is, I have 10 people in a group. The group needs to be split into 2 groups with a minimum group size of 4. So groups of either 4-6 or 5-5 for a problem size of 10.

Now the group needs to be split fairly so that as many people are happy with the people that are in their group as possible.

I can get the group to either put the other 9 people in sequential order of how much they want to be with that person or give them a rating of say 1-10 of how much they want to be with that person.

How do I solve this problem?

Upvotes: 0

Views: 659

Answers (1)

R. Martinho Fernandes
R. Martinho Fernandes

Reputation: 234434

Since there are only a few combinations possible, an exhaustive algorithm might be good enough.

You need to generate all the combinations and maximize the "total group happiness". You'll have to come up with some heuristic for this "total group happiness" thing. If you use the rating system you suggested, one idea is to just go through each group, and sum all the ratings for pairs of its members.

Another solution would be to construct a linear programming model that maximizes the group happiness function and then optimize it.

Upvotes: 2

Related Questions