Here is the problem:
There are $MN$ people, where there are $M$ seeds and $N$ people are in each seed.
We have to make a team of $M$ people where everyone in the team have different seeds.
Each person have their own value; the seeds are aligned so that for any seeds $I$ and $J$ and for any $ain I$ and $bin J$, $a<b$ or $a>b$ holds. Assume there are no two people with same values.
- People assign individually.
- People may assign individually or as a couple. In the latter case these two should be in the same team.
For each cases, design an algorithm to make the variance of the sum of each teams to be minimum.
Well, the problem above is the optimal solution, and since it 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! Thanks!
Edit: All values of each person are positive integers.