4

Problem: Given a list L of objects of possible sizes from set S={1,2,4,8} and unlimited supply of bins of sizes 16 each and we have to use minimum possible numbers of bins to pack all objects of L.
I am also searching for an optimal (or near optimal) solution using dynamic programming or otherwise in the following scenarios when

  1. L is not given offline, instead we are asked to fit objects one by one without knowing future requests(1-D online vector bin packing).
  2. sizes can be from SXS and bins are of capacity (16,16) each. (2-D vector bin packing).

Assumption: Optimal packing means the best possible packing from all possible packing i.e the packing with the minimum numbers of bins used.
Actually generalized vector bin packing is NP-hard, but I think due standard sizes from finite set, more efficient and better solutions may exist.

My approach: Clearly, 1-D offline can packed in <=optimal+1 using clever pairing of objects .
But I am stuck for the other 2 aspects asked above.
I know about First Fit,Best Fit, First Fit Decreasing algorithms but I am searching for this problem specific solution.

1

For the 1-Dimensional offline case, suppose you sort all objects from large to small. Due to the sizes, no nasty cutoffs will occur, and all bins except for maybe the last one will be filled to full capacity. I guess this is what you mean with the clever pairing.

For the online case, if you keep 4 different bins, one for each size, then you will be able to fill every bin completely except for maybe 4 bins. If the list is large enough, this will be very close to an optimal solution. Are the size of the list L and the probability of each size occuring known in advance?

  • Welcome to the site. I'm not sure if you noticed that the question you are answering is more than 2 years old. While your answer seems to be relevant and helpful, please don't be discouraged if you don't get any further feedback on it. – JimmyJames Aug 31 '16 at 20:58
  • Thank you for the comment. It is really nice to get some feedback on whether my answer could be helpful/relevant. Especially as a new guy :) – FlorianK Sep 3 '16 at 8:10

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.