Just a question I have been pondering.
Assume you have a class of 100 students, each student chooses 3 friends. The goal is to split them into 4 groups of 25.
We define 'satisfaction level of student j', $ s_j=i/3$ where i is the amount of friends in the same group.
I'd like to find an efficient algorithm to split the class so that the average satisfaction is highest possible, and the number of students j with $s_j=0$ is lowest.
My initial thoughts were finding a way to use gale-shapely, or finding connected objects in a directed graph.
Any thoughts?