# A problem similar to the Bin packing problem?

I'm working on a problem that is very similar to the bin packing problem, but for me, the objective is to minimize the maximum weight given m bins. The problem statement is:

Given n items, each with a certain weight less than some maximum weight (w_max), how do you pack them into m bins so that you minimize the maximum weight (over all bins)?

I'm looking at a possible approach that would simply iterate by grouping the two smallest weight items until the number of groups equals the number of bins.

Has anyone heard of a similar problem and know of an approach to solve this with some guarantees?

• I forgot to mention that there is no restriction in terms of bin capacity (i.e. can be infinite). Jul 19, 2017 at 17:49
• It seems like a variant of multiway number partitioning. You may find some references here: en.wikipedia.org/wiki/Multiway_number_partitioning Jun 11, 2021 at 14:11

One way to solve your problem is to use binary search over the maximum weight. In other words, pick a threshold $t$, and check whether it's possible to pack your items into $m$ bins, without using more than a total weight of $t$ in each bin. This is exactly the bin packing problem: is it possible to pack the items into $m$ bins of capacity $t$? You can apply any algorithm for bin packing to this problem. Then, use binary search on $t$.