An asymptotic competitive scheme for online bin packing

Lin Chen, Deshi Ye, Guochuan Zhang

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


In the online bin packing problem, a list of items with integral sizes between 1 to B arrive one by one. Each item must be irrevocably assigned into a bin of capacity B upon its arrival without any information on the subsequent items, and the goal is to minimize the number of used bins. In this paper, we deal with online bin packing from a new sight. 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. Apart from the technical results, the analysis to bridge the online and the off-line approaches might be of particular interests.

Original languageEnglish
Pages (from-to)446-454
Number of pages9
JournalTheoretical Computer Science
StatePublished - Nov 1 2015


  • Bin packing
  • Competitive scheme
  • Online algorithms


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

Cite this