1
$\begingroup$

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:

  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!

$\endgroup$
2
  • $\begingroup$ @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. $\endgroup$ Nov 23 '20 at 7:00
  • $\begingroup$ 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). $\endgroup$ Nov 23 '20 at 7:24
1
$\begingroup$

If you're willing to replace 'variance' with 'max minus min' (spread), then you could formulate this as an instance of integer linear programming and apply an off-the-shelf ILP solver. There is no guarantee that it finds an optimal solution in a reasonable amount of time, but if you're lucky, it might complete without taking too long; or if you stop it early, you might get a decent solution.

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.

If you want to use the variance, this becomes a mixed-integer quadratic program instead of a mixed-integer linear program, and I think quadratic programs are significantly harder.

$\endgroup$
1
  • $\begingroup$ Thanks! For those who are interested in how I made the program, I used or-tools from google. $\endgroup$ Dec 4 '20 at 4:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.