Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
483019 | European Journal of Operational Research | 2007 | 10 Pages |
Abstract
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 < C ⩽ 6, and at most 1 + ⌊(C − 1)/3⌋ if C > 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 Gilmore–Gomory formulation.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Carlo Filippi,