Cover Image

An asymptotic approximation scheme for the concave cost bin packing problem

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 [epsilon], there exists a polynomial-time approximation algorithm with an asymptotic worst-case performance ratio of no more than 1 + [epsilon].
Year of publication:
2008
Authors: Leung, Joseph Y.-T. ; Li, Chung-Lun
Published in:
European Journal of Operational Research. - Elsevier, ISSN 0377-2217. - Vol. 191.2008, 2, p. 582-586
Publisher: Elsevier
Type of publication: Article
Source:
Persistent link: https://ebvufind01.dmz1.zbw.eu/10005283791
Similar items by person