Suppose there're $N$ weighted balls and $M$ equal weight bins, it's guaranteed at least one placement exists that all the balls can be placed into bins.

What's the right algorithm to achieve a well-balanced placement where each bin has almost equal weights of balls?

I know if the bins are of different weights, the problem is NP-hard; Not sure a simplified question can be solved in linear time.

I'd appreciate any references where I could find some papers discussing the complexity and solutions related. Thank you!

  • 4
    $\begingroup$ It's already NP-hard for $M=2$: if you make the 2 equal-capacity bins sufficiently large, this is the Partition Problem. $\endgroup$ Commented Aug 22, 2019 at 21:41
  • $\begingroup$ This problem is similar to minimizing makespan on M uniform processors. I believe that if the number of distinct ball sizes is $k$, you can solve this problem in $O(n^{2k})$. See appendix here courses.engr.illinois.edu/cs583/sp2018/Notes/… In this case, however, we are looking at the $L^{\infty}$ norm, whereas in your case it is unclear which norm you desire. $\endgroup$ Commented Aug 23, 2019 at 13:27


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.