An asymptotic competitive scheme for online bin packing

Lin Chen, Deshi Ye, Guochuan Zhang

Research output: Contribution to journalArticlepeer-review

Abstract

We study the online bin packing problem, in which a list of items with integral size between 1 to B arrives one at a time. Each item must be assigned in a bin of capacity B upon its arrival without any information on the next items, and the goal is to minimize the number of used bins. We present an asymptotic competitive scheme, i.e., for any ε > 0, the asymptotic competitive ratio is at most ρ + _, where ρ is the smallest possible asymptotic competitive ratio among all online algorithms.

Keywords

  • Bin packing
  • Competitive scheme
  • Online algorithms

Fingerprint Dive into the research topics of 'An asymptotic competitive scheme for online bin packing'. Together they form a unique fingerprint.

Cite this