# Algorithms of placing N weighted balls into M uniform bins while striving for balanced weight?

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!

• It's already NP-hard for $M=2$: if you make the 2 equal-capacity bins sufficiently large, this is the Partition Problem. Commented Aug 22, 2019 at 21:41
• 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. Commented Aug 23, 2019 at 13:27