TY - GEN
T1 - On the advice complexity of one-dimensional online bin packing
AU - Zhao, Xiaofan
AU - Shen, Hong
N1 - Funding Information:
This work is supported by National Science Foundation of China under its General Projects funding #61170232, State Key Laboratory of Rail Traffic Control and Safety independent research grant RS2012K011, and Sun Yat-sen University 985 Project funding.
PY - 2014
Y1 - 2014
N2 - In this paper, we study the problem of the online bin packing with advice. Assume that there is an oracle with infinite computation power which can provide specific information with regard to each incoming item of the online bin packing problem. With this information, we want to pack the list L of items, one at a time, into a minimum number of bins. The bin capacity is 1 and all items have size no larger than 1. The total size of packed items in each bin cannot exceed the bin capacity. Inspired by Boyar et al's work [1] of competitive ratio [1] with two advice bits per item., we show that if the oracle provides three bits of advice per item, applying a different item classification scheme from Boyar et al's we can obtain an online algorithm with competitive ratio 5/4OPT + 2 to pack list L.
AB - In this paper, we study the problem of the online bin packing with advice. Assume that there is an oracle with infinite computation power which can provide specific information with regard to each incoming item of the online bin packing problem. With this information, we want to pack the list L of items, one at a time, into a minimum number of bins. The bin capacity is 1 and all items have size no larger than 1. The total size of packed items in each bin cannot exceed the bin capacity. Inspired by Boyar et al's work [1] of competitive ratio [1] with two advice bits per item., we show that if the oracle provides three bits of advice per item, applying a different item classification scheme from Boyar et al's we can obtain an online algorithm with competitive ratio 5/4OPT + 2 to pack list L.
KW - bin packing
KW - competitive ratio
KW - computation with advice
KW - online algorithm
UR - http://www.scopus.com/inward/record.url?scp=84903608896&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-08016-1_29
DO - 10.1007/978-3-319-08016-1_29
M3 - Conference contribution
AN - SCOPUS:84903608896
SN - 9783319080154
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 320
EP - 329
BT - Frontiers in Algorithmics - 8th International Workshop, FAW 2014, Proceedings
PB - Springer Verlag
T2 - 8th International Frontiers of Algorithmics Workshop, FAW 2014
Y2 - 28 June 2014 through 30 June 2014
ER -