TY - JOUR
T1 - An asymptotic competitive scheme for online bin packing
AU - Chen, Lin
AU - Ye, Deshi
AU - Zhang, Guochuan
N1 - Publisher Copyright:
© 2015 Elsevier B.V.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.
PY - 2015/11/1
Y1 - 2015/11/1
N2 - 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.
AB - 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.
KW - Bin packing
KW - Competitive scheme
KW - Online algorithms
UR - http://www.scopus.com/inward/record.url?scp=84984923997&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2015.04.038
DO - 10.1016/j.tcs.2015.04.038
M3 - Article
AN - SCOPUS:84984923997
VL - 607
SP - 446
EP - 454
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -