TY - JOUR
T1 - An asymptotic competitive scheme for online bin packing
AU - Chen, Lin
AU - Ye, Deshi
AU - Zhang, Guochuan
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2014.
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
KW - Bin packing
KW - Competitive scheme
KW - Online algorithms
UR - http://www.scopus.com/inward/record.url?scp=84921520304&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-12691-3_2
DO - 10.1007/978-3-319-12691-3_2
M3 - Article
AN - SCOPUS:84921520304
SN - 0302-9743
VL - 8881
SP - 13
EP - 24
JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ER -