<p>There are $n$ bins and $m$ balls, $b_i$ where $0&lt;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&lt;n$ bins so that maximal load of these bins is minimized.</p>

CC BY-SA 3.0
2011-06-28T20:09:05.590Z
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.
Suresh Venkat
CC BY-SA 3.0
2011-06-28T21:19:31.930Z
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...
Richard
CC BY-SA 3.0
2011-06-28T21:47:25.833Z
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.
singhsumit
CC BY-SA 3.0
2011-06-29T05:03:36.727Z
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 ;-).
Marek Chrobak
CC BY-SA 3.0
2011-06-29T13:07:59.253Z
@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?
Richard
CC BY-SA 3.0
2011-06-30T16:48:32.867Z
@Richard you can determine whether there is an assignment with maximum load at most $k$ in linear time.
Dave
<ds.algorithms><optimization><packing>
On algorithms that minimizes maximal load of bins
Richard
# On algorithms that minimizes maximal load of bins

(Asked by: username_0 on 2011-06-28)

There are $n$ bins and $m$ balls, $b\_i$ where $0

**Tags:** ds.algorithms, optimization, packing

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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...  
> **username_2**: 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.  
> **username_3**: 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 ;-).  
> **username_0**: @username_2 this is not bin packing problem since here # of bins is fixed and what to optimize is the bin size... @username_3, could you give a hint on solution?  
> **username_4**: @username_0 you can determine whether there is an assignment with maximum load at most $k$ in linear time.  

---

## 0 answers

