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.

  • 1
    $\begingroup$ 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. $\endgroup$ Jun 28 '11 at 20:09
  • $\begingroup$ 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... $\endgroup$
    – Richard
    Jun 28 '11 at 21:19
  • $\begingroup$ 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. $\endgroup$
    – singhsumit
    Jun 28 '11 at 21:47
  • 1
    $\begingroup$ 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 ;-). $\endgroup$ Jun 29 '11 at 5:03
  • $\begingroup$ @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? $\endgroup$
    – Richard
    Jun 29 '11 at 13:07

Your Answer

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

Browse other questions tagged or ask your own question.