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

Research output: Journal article publication › Journal article › Academic research › peer-review

15 Citations (Scopus)

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
Pages (from-to)	581-585
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
Publication status	Published - 1 Dec 2008

Keywords

Asymptotic worst-case analysis
Bin packing
Concavity

ASJC Scopus subject areas

Information Systems and Management
Management Science and Operations Research
Statistics, Probability and Uncertainty
Applied Mathematics
Modelling and Simulation
Transportation

More information

10.1016/j.ejor.2007.08.031

http://hdl.handle.net/10397/1845

Cite this

@article{5ed967c162a9490da69d278e9f9d2fe0,

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

year = "2008",

month = dec,

day = "1",

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

language = "English",

volume = "191",

pages = "581--585",

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

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

U2 - 10.1016/j.ejor.2007.08.031

DO - 10.1016/j.ejor.2007.08.031

M3 - Journal article

SN - 0377-2217

VL - 191

SP - 581

EP - 585

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

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this