@inproceedings{395e31fea80a4064b5f3b1e3f0b41f54,
title = "Improved online algorithms for one-dimensional BinPacking with advice",
abstract = "In this paper, we study the problem of 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 the work of Boyar et al. of competitive ratio 4/3 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 als, we can obtain an online algorithm with competitive ratio 5/4 to pack list L. Furthermore, we show that our algorithm can retain the same competitive ratio 5/4 with only two advice bits per item, hence improving the known result.",
keywords = "Bin packing, Competitive ratio, Computation with advice, Online algorithm",
author = "Xiaofan Zhao and Xin Li and Hong Shen",
note = "Publisher Copyright: {\textcopyright} 2017 IEEE.; 18th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2017 ; Conference date: 18-12-2017 Through 20-12-2017",
year = "2017",
month = jul,
day = "2",
doi = "10.1109/PDCAT.2017.00042",
language = "English",
series = "Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings",
publisher = "IEEE Computer Society",
pages = "211--216",
editor = "Shi-Jinn Horng",
booktitle = "Proceedings - 18th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2017",
address = "United States",
}