0

This is an example to illustrate the problem. Imagine you have to make two groups of 5 students each from a classroom of 50 students. Students differ on three grades: math, physics, and language (all have the same unit of measure). The goal is to make the two groups as similar as possible considering these three dimensions. That is, simultaneously minimize the average difference for each dimension between groups.

I solved this numerically by randomly sampling the students and computing each group's mean on each dimension and comparing these means between groups as to minimize them. As you can imagine this solution is far from ideal.

Is there an analytical way to solve this problem? Is there a general solution for D dimensions, n students per groups, and a pool of N students from which to pick?

mat
  • 101
  • 1
    So, each student is representable as a unit-weight point in an D-dimensional space at coordinates reflecting their respective grades; and you want to select two (disjoint) subsets, n-elements each, so that their respective barycenters are as close to one another as possible. Well, it's a nice problem, but I have no idea how to solve it. – CiaPan May 27 '20 at 11:57
  • @CiaPan Thanks for formulating it more precisely. You nailed it down. – mat May 27 '20 at 12:07
  • 1
    Here's a much simpler problem that doesn't have a good solution: given a (finite) bunch of (whole) numbers, partition it into two subsets whose sums are as equal as possible. The problem is NP-complete, so no one has a good algorithm for solving it. See https://en.wikipedia.org/wiki/Subset_sum_problem – Gerry Myerson May 27 '20 at 12:20
  • @GerryMyerson Thanks for that. – mat May 27 '20 at 13:44

0 Answers0