Here is the problem:
There are $MN$ people, where there are $M>1$ seeds and $N>0$ people are in each seed. We have to make $N$ teams of $M$ people where everyone in the team have different seeds. Each person have their own value; values are positive integers. Assume there are no two people with same values.
For two distinct seeds $I$ and $J$, we say $I<J$ if for all $x\in I$ and $y\in J$, $x<y$ holds. It is guaranteed that for any two distinct seeds $I$ and $J$ in the problem, $I<J$ or $J<I$ holds. In other words, we can set $M$ seeds $I_1,I_2,\cdots,I_M$ in the problem to satisfy $I_1<I_2<\cdots<I_M$.
I am interested in two versions of this problem:
- There are no paired people. This means in process of making $N$ teams, there is no restriction except given above.
- There may be some paired people. This means a set of paired people that cannot be split is given, so that if a team contains one person from some pair, the team should also contain the other person from that pair. It is provided that every pair contains exactly two people from different seeds.
For each version, the task is to design an algorithm to make the variance of the sum of values of people in each team to be minimum.
Since this problem is NP (complete?), I would accept heuristics. I hope that the heuristic method gives the solution with variance at most $25\%$ larger than the optimal solution, as I don't want to harm the balance of the team.
Could you please give an algorithm or heuristic that can solve this problem? Also, adding a time complexity would be highly appreciated!