# On algorithms that minimizes maximal load of bins

There are $n$ bins and $m$ balls, $b_i$ where $0<i\le m$. Balls are with different weights $w_i$ and have dependency between them. ball $b_1$ depends on $b_2$, $b_2$ depends on $b_3$, and so on. It means that $b_1$ can be assigned with $b_3$ only when $b_2$ is assigned to the same bin. Is there an algorithm that assigns balls into $x<n$ bins so that maximal load of these bins is minimized.

• The dependency structure is not entirely clear to me. Does "i depends on j" mean that i can be assigned to a bucket only if j is ? Because in the example you provide, I can only see why ONE of $b_1$ or $b_3$ depends on $b_2$, not both. Jun 28 '11 at 20:09
• it means there is order between balls. it's ok to have ball 1, 2, 3 being assigned to three different buckets, but 1, 2 to one buckets and 3 to another buckets. But once 1,3 are assigned to one bucket, 2 must be assigned to that one too... Jun 28 '11 at 21:19
• are there many balls that can depend on one or more ball(s)? If ball $b_i$ depends on $b_{i+1}$ then the problem seems trivial but otherwise in general, if every ball depends on another then it's standard bin packing problem. Jun 28 '11 at 21:47
• It appears that you want to compute a packing where each bin contains consecutive balls, $b_i$, $b_{i+1}$ ,..., $b_j$, correct? If this is what you mean, the answer is "yes", this can be solved efficiently, but this also sounds a lot like a homework problem ;-). Jun 29 '11 at 5:03
• @singhsumit this is not bin packing problem since here # of bins is fixed and what to optimize is the bin size... @Marek Chrobak, could you give a hint on solution? Jun 29 '11 at 13:07