splitting of people betwen groups with group prioritiy list per person

Computer Science Asked by Gomunkul on December 15, 2020

Looking for an algorithm for splitting a list of people (S) into groups (G), |S| <= |G|, more than one person wants to be in a certain group.
Every person has a monotone ranking from highest (most desired) to lowest of all the groups.
Using this list I want to find the "best matching".
"best matching" is when you maximize the "score of the matching".
"score of the matching" is the sum of the group rankings of the people that got matched with the group, i.e. summing the ranking that the people gave to the group which was chosen for them.

I’m also interested in ideas for other "fairness" values for maximization.

One Answer

If you want to maximize the sum of the scores for each participant, this is an instance of the assignment problem; use the Hungarian algorithm, or any other algorithm for computing a maximum matching.

You might also be interested in stable marriage algorithms, which have a different notion of fairness.

Answered by D.W. on December 15, 2020

Add your own answers!

Ask a Question

Get help from others!

© 2024 All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP