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!

Related Questions

How to generate graphs with a Hamiltonian path?

3  Asked on February 21, 2021 by always-newbie


Wifi throughput calculation

1  Asked on February 20, 2021 by copsa


Thirty-one game. Prediction of the winner

1  Asked on February 17, 2021 by donvitomarco


speed of preorder traversal

1  Asked on February 8, 2021 by keith-paton


Mergesort and some claims on comparison

1  Asked on February 7, 2021 by user3661613


Proving the language of non-primes is in NP

1  Asked on February 6, 2021 by builderthebob00


Longest path on a full tree

1  Asked on January 27, 2021 by bm1125


Ask a Question

Get help from others!

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