On the bin packing problem with a fixed number of object weights
We consider a bin packing problem where the number of different object weights is fixed to C. We analyze a simple approximate approach and show that it leads to an asymptotically exact polynomial algorithm with absolute error 0 if C=2, at most 1 if 1 6. A consequence of our analysis is a new upper bound on the gap between the optimal value of the problem at hand and the round-up of the optimal value of the linear relaxation of its GilmoreGomory formulation.
bin packing cutting stock high-multiplicity integer round-up property