Please see this question and answer to a very similar question:

http://stackoverflow.com/a/39338999/1060350

Here, there was a requirement that nearby pairs of points should be formed and put into separate groups (avoid the term cluster when they aren't regular clusters). But this should even further improve your requirement.

A similar, surprising, heuristic for your aim of attempting to have 0 mean is this:

1. Sort points by the distance from the center (here 0).
2. Choose the farthest point $x$ in this list, and the point $y$ which minimizes $||x+y||_2$
3. Assign both randomly to cluster A or B
4. Repeat 2 (only), but assign them to the other cluster.
5. If there are more than 3 points remaining, go back to 2
6. Assign the remaining points according to your size constraints and use them to slightly improve the means to your liking.

This is only a heuristic - it will not find the optimum solution - but probsbly the problem is NP or exponential, so you can't afford to search for the optimum.

Above greedy approach should find a decent solution, because it tries to identify the hardest points first, then chooses the best counterbalance each.

If you need better results, you can modify step 3 to not choose at random, but instead assign points to clusters as to minimize how much the cluster center deviates from 0. This could also be used in step 2: instead of minimizing $||x+y||_2$ you could minimize $||C+x+y||_2$ where C are all the objects already in the cluster. These tweaks make the code slightly more complicated, but require not much computational overhead.

Please see this question and answer to a very similar question:

https://stackoverflow.com/a/39338999/1060350

Here, there was a requirement that nearby pairs of points should be formed and put into separate groups (avoid the term cluster when they aren't regular clusters). But this should even further improve your requirement.

A similar, surprising, heuristic for your aim of attempting to have 0 mean is this:

1. Sort points by the distance from the center (here 0).
2. Choose the farthest point $x$ in this list, and the point $y$ which minimizes $||x+y||_2$
3. Assign both randomly to cluster A or B
4. Repeat 2 (only), but assign them to the other cluster.
5. If there are more than 3 points remaining, go back to 2
6. Assign the remaining points according to your size constraints and use them to slightly improve the means to your liking.

This is only a heuristic - it will not find the optimum solution - but probsbly the problem is NP or exponential, so you can't afford to search for the optimum.

Above greedy approach should find a decent solution, because it tries to identify the hardest points first, then chooses the best counterbalance each.

If you need better results, you can modify step 3 to not choose at random, but instead assign points to clusters as to minimize how much the cluster center deviates from 0. This could also be used in step 2: instead of minimizing $||x+y||_2$ you could minimize $||C+x+y||_2$ where C are all the objects already in the cluster. These tweaks make the code slightly more complicated, but require not much computational overhead.

Pleas see this question and answer to a very similar question:

http://stackoverflow.com/a/39338999/1060350

Here, there was a requirement that nearby pairs of points should be formed and put into separate groups (avoid the term cluster when they aren't regular clusters). But this should even further improve your requirement.

A similar, surprising, heuristic for your aim of attempting to have 0 mean is this:

1. Sort points by the distance from the center (here 0).
2. Choose the farthest point $x$ in this list, and the point $y$ which minimizes $||x+y||_2$
3. Assign both randomly to cluster A or B
4. Repeat 2 (only), but assign them to the other cluster.
5. If there are more than 3 points remaining, go back to 2
6. Assign the remaining points according to your size constraints and use them to slightly improve the means to your liking.

This is only a heuristic - it will not find the optimum solution - but probsbly the problem is NP or exponential, so you can't afford to search for the optimum.

Above greedy approach should find a decent solution, because it tries to identify the hardest points first, then chooses the best counterbalance each.

If you need better results, you can modify step 3 to not choose at random, but instead assign points to clusters as to minimize how much the cluster center deviates from 0. This could also be used in step 2: instead of minimizing $||x+y||_2$ you could minimize $||C+x+y||_2$ where C are all the objects already in the cluster. These tweaks make the code slightly more complicated, but require not much computational overhead.

Please see this question and answer to a very similar question:

http://stackoverflow.com/a/39338999/1060350

Here, there was a requirement that nearby pairs of points should be formed and put into separate groups (avoid the term cluster when they aren't regular clusters). But this should even further improve your requirement.

A similar, surprising, heuristic for your aim of attempting to have 0 mean is this:

1. Sort points by the distance from the center (here 0).
2. Choose the farthest point $x$ in this list, and the point $y$ which minimizes $||x+y||_2$
3. Assign both randomly to cluster A or B
4. Repeat 2 (only), but assign them to the other cluster.
5. If there are more than 3 points remaining, go back to 2
6. Assign the remaining points according to your size constraints and use them to slightly improve the means to your liking.

This is only a heuristic - it will not find the optimum solution - but probsbly the problem is NP or exponential, so you can't afford to search for the optimum.

Above greedy approach should find a decent solution, because it tries to identify the hardest points first, then chooses the best counterbalance each.

If you need better results, you can modify step 3 to not choose at random, but instead assign points to clusters as to minimize how much the cluster center deviates from 0. This could also be used in step 2: instead of minimizing $||x+y||_2$ you could minimize $||C+x+y||_2$ where C are all the objects already in the cluster. These tweaks make the code slightly more complicated, but require not much computational overhead.