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

An asymptotic approximation scheme for the concave cost bin packing problem

Joseph Y.T. Leung, Chung Lun Li

Computer Science

Research output: Contribution to journal › Article › peer-review

15 Scopus citations

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}.

Original language	English (US)
Pages (from-to)	582-586
Number of pages	5
Journal	European Journal of Operational Research
Volume	191
Issue number	2
DOIs	https://doi.org/10.1016/j.ejor.2007.08.031
State	Published - Dec 1 2008

All Science Journal Classification (ASJC) codes

General Computer Science
Modeling and Simulation
Management Science and Operations Research
Information Systems and Management

Keywords

Asymptotic worst-case analysis
Bin packing
Concavity

Access to Document

10.1016/j.ejor.2007.08.031

Cite this

@article{874b1345d2284d57bac5262e5a7ccf91,

title = "An asymptotic approximation scheme for the concave cost bin packing problem",

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}.",

keywords = "Asymptotic worst-case analysis, Bin packing, Concavity",

author = "Leung, {Joseph Y.T.} and Li, {Chung Lun}",

note = "Funding Information: 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.",

year = "2008",

month = dec,

day = "1",

doi = "10.1016/j.ejor.2007.08.031",

language = "English (US)",

volume = "191",

pages = "582--586",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - An asymptotic approximation scheme for the concave cost bin packing problem

AU - Leung, Joseph Y.T.

AU - Li, Chung Lun

N1 - Funding Information: 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.

PY - 2008/12/1

Y1 - 2008/12/1

N2 - 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}.

AB - 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}.

KW - Asymptotic worst-case analysis

KW - Bin packing

KW - Concavity

UR - http://www.scopus.com/inward/record.url?scp=43849104606&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=43849104606&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2007.08.031

DO - 10.1016/j.ejor.2007.08.031

M3 - Article

AN - SCOPUS:43849104606

SN - 0377-2217

VL - 191

SP - 582

EP - 586

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 2

ER -

An asymptotic approximation scheme for the concave cost bin packing problem

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this