An asymptotic competitive scheme for online bin packing

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.