Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
477463 | European Journal of Operational Research | 2008 | 5 Pages |
Abstract
We consider a generalized one-dimensional bin packing model in which the cost of a bin is a nondecreasing concave function of the utilization of the bin. We show that for any given positive constant ϵ, there exists a polynomial-time approximation algorithm with an asymptotic worst-case performance ratio of no more than 1 + ϵ.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Joseph Y.-T. Leung, Chung-Lun Li,