An asymptotic competitive scheme for online bin packing

Lin Chen, Deshi Ye, Guochuan Zhang

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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
Volume607
DOIs
StatePublished - Nov 1 2015

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