2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I forgot to mention that there is no restriction in terms of bin capacity (i.e. can be infinite). $\endgroup$ – KshMny Jul 19 '17 at 17:49
1
$\begingroup$

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

Be warned that it is NP-hard, so don't expect an efficient algorithm that produces the optimal solution in a reasonable amount of time for large problem instances.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.