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 ε{lunate}, there exists a polynomial-time approximation algorithm with an asymptotic worst-case performance ratio of no more than 1 + ε{lunate}. © 2007 Elsevier B.V. All rights reserved.
| Original language | English |
|---|---|
| Pages (from-to) | 582-586 |
| Journal | European Journal of Operational Research |
| Volume | 191 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - 1 Dec 2008 |
| Externally published | Yes |
Bibliographical note
Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].Funding
This research was supported in part by the Research Grants Council of Hong Kong under Grant PolyU5312/04E. The work of the first author was supported in part by the National Science Foundation under Grants DMI-0300156 and DMI-0556010.
Research Keywords
- Asymptotic worst-case analysis
- Bin packing
- Concavity