An asymptotic approximation scheme for the concave cost bin packing problem

Joseph Y T Leung, Chung Lun Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 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 languageEnglish
Pages (from-to)581-585
Number of pages5
JournalEuropean Journal of Operational Research
Volume191
Issue number2
DOIs
Publication statusPublished - 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

Cite this