In the allocation of objects in boxes, how to minimize the variance of total weights of the boxes?

80 Views Asked by At

There are N boxes (indexed as n1, n2, n3, etc.), and M objects of different positive weights each (weights m1, m2, m3, etc. The objects are ordered in a way so m1≥m2≥m3≥...).

The objective is allocating all the objects, so each object is inside exactly in one box, in a way that makes the total weight (sum of the weights of the objects they contain) of all the boxes as equal as possible (with the error to minimize being the variance of the total weights).

A way to allocate the objects is:

With all boxes initially empty, for i from 1 to M do: Pick up object with weight mi, and place it inside the box that currently has the smallest total weight (if there is more than one, choose any of the boxes that have the smallest total weight).

This method seems to minimize the error quite well, but I haven't figured out any proof, or counterexample, of it actually being the most optimal solution to the problem in all cases.

1

There are 1 best solutions below

0
On

It is good but not always the best:

Suppose you start with $\{3,4,6,7,8\}$ and want to split into two sets

Your simple algorithm gives $8+4+3=15$ and $7+6=13$

while $8+6=14$ and $7+4+3=14$ is better