Forming Beneficial Teams of Students in Massive Online Classes

Given a class of large number of students, each exhibiting a different ability level, how can we form teams of students so that the expected performance of team members improves due to team participation? We take a computational perspective and formally define two versions of such team-formation problem: the MaxTeam and the MaxPartition problems. The first asks for the identification of a single team of students that improves the performance of most of the participating team members. The second asks for a partitioning of students into non-overlapping teams that also maximizes the benefit of the participating students. We show that the first problem can be solved optimally in polynomial time, while the second is NP-complete. For the MaxPartition problem, we also design an efficient approximate algorithm for solving it. Our experiments with generated data coming from different distributions demonstrate that our algorithm is significantly better than any of the popular strategies for dividing students in a class into sections.