An asymptotic approximation scheme for the concave cost bin packing problem

Joseph Y.T. Leung, Chung Lun Li

Research output: Contribution to journalArticlepeer-review

9 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 languageEnglish (US)
Pages (from-to)582-586
Number of pages5
JournalEuropean Journal of Operational Research
Volume191
Issue number2
DOIs
StatePublished - Dec 1 2008

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Keywords

  • Asymptotic worst-case analysis
  • Bin packing
  • Concavity

Fingerprint

Dive into the research topics of 'An asymptotic approximation scheme for the concave cost bin packing problem'. Together they form a unique fingerprint.

Cite this