An asymptotic approximation scheme for the concave cost bin packing problem

Joseph Y.-T. Leung; Chung-Lun Li

doi:10.1016/j.ejor.2007.08.031

Author(s)

Joseph Y.-T. Leung
Chung-Lun Li

Detail(s)

Original language	English
Pages (from-to)	582-586
Journal / Publication	European Journal of Operational Research
Volume	191
Issue number	2
Publication status	Published - 1 Dec 2008
Externally published	Yes

Link(s)

DOI	DOI https://doi.org/10.1016/j.ejor.2007.08.031 Final Published version
	Check@CityULib
Link to Scopus	https://www.scopus.com/record/display.uri?eid=2-s2.0-43849104606&origin=recordpage
Permanent Link	https://scholars.cityu.edu.hk/en/publications/publication(fc7574c0-4574-458c-b3a5-78009ccf37c9).html

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.

Research Area(s)

Asymptotic worst-case analysis, Bin packing, Concavity

Bibliographic 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].

Citation Format(s)

[ RIS ] [ BibTeX ]

An asymptotic approximation scheme for the concave cost bin packing problem. / Leung, Joseph Y.-T.; Li, Chung-Lun.
In: European Journal of Operational Research, Vol. 191, No. 2, 01.12.2008, p. 582-586.

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

Leung, JY-T & Li, C-L 2008, 'An asymptotic approximation scheme for the concave cost bin packing problem', European Journal of Operational Research, vol. 191, no. 2, pp. 582-586. https://doi.org/10.1016/j.ejor.2007.08.031

Leung, J. Y.-T., & Li, C.-L. (2008). An asymptotic approximation scheme for the concave cost bin packing problem. European Journal of Operational Research, 191(2), 582-586. https://doi.org/10.1016/j.ejor.2007.08.031

Leung JYT, Li CL. An asymptotic approximation scheme for the concave cost bin packing problem. European Journal of Operational Research. 2008 Dec 1;191(2):582-586. doi: 10.1016/j.ejor.2007.08.031

Leung, Joseph Y.-T. ; Li, Chung-Lun. / An asymptotic approximation scheme for the concave cost bin packing problem. In: European Journal of Operational Research. 2008 ; Vol. 191, No. 2. pp. 582-586.