# 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). – KshMny Jul 19 '17 at 17:49

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$.