# How can I make the variance of a multiple sum of set of fixed number of variables minimum?

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 if for all $$x\in I$$ and $$y\in J$$, $$x holds. It is guaranteed that for any two distinct seeds $$I$$ and $$J$$ in the problem, $$I or $$J holds. In other words, we can set $$M$$ seeds $$I_1,I_2,\cdots,I_M$$ in the problem to satisfy $$I_1.

I am interested in two versions of this problem:

1. There are no paired people. This means in process of making $$N$$ teams, there is no restriction except given above.
2. 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!

• @D.W. Yes, the seeds given will have that property. For clarification, the example of seeds are $\{1000, 1005\},\{1007, 1008\}$, as $\{1000, 1005\} < \{1007, 1008\}$. But there will be no input like $\{1000, 1007\},\{1005, 1008\}$, as $\{1000, 1007\} < \{1005, 1008\}$ nor $\{1000, 1007\} > \{1005, 1008\}$ does not hold. Nov 23 '20 at 7:00
• We are running an N vs N match. We have set a value to determine one's stat, and set the team's stat as the sum of each players in the team. The staffs have to make a team based on two conditions given above, as players are not allowed to make a team (think of the situation where best players of each seed makes a team). Nov 23 '20 at 7:24

To formulate this as an instance of ILP, add zero-or-one variables $$x_{i,j}$$, with the intended meaning that $$x_{i,j}=1$$ means that person $$i$$ is assigned to team $$j$$. Each requirement in the problem statement can be expressed as a linear inequality; for instance, the requirement that everyone in a team has a different can be expressed by inequalities of the form $$x_{i,j} + x_{i',j} \le 1$$ for each pair $$i,i'$$ of people from the same seed.
To minimize the spread, introduce variables $$\ell,u$$. Let $$v_i$$ denote the value of person $$i$$ (this is a constant, not a variable). Add linear inequalities $$\ell \le \sum_i x_{i,j} v_i \le u$$ for each team $$j$$. Finally, minimize $$u-\ell$$, subject to the inequalities above.