Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/88764
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | On the advice complexity of one-dimensional online bin packing |
Author: | Zhao, X. Shen, H. |
Citation: | Lecture Notes in Artificial Intelligence, 2014 / Chen, J., Hopcroft, J., Wang, J. (ed./s), vol.8497 LNCS, pp.320-329 |
Publisher: | Springer Verlag |
Issue Date: | 2014 |
Series/Report no.: | Lecture Notes in Computer Science; 8497 |
ISBN: | 9783319080154 |
ISSN: | 0302-9743 1611-3349 |
Conference Name: | International Frontiers of Algorithmics Workshop (FAW) (28 Jun 2014 - 30 Jun 2014 : Zhangjiajie, China) |
Editor: | Chen, J. Hopcroft, J. Wang, J. |
Statement of Responsibility: | Xiaofan Zhao and Hong Shen |
Abstract: | 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 43 [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 54OPT+2 to pack list L. |
Keywords: | bin packing online algorithm computation with advice competitive ratio |
Rights: | © Springer International Publishing Switzerland 2014 |
DOI: | 10.1007/978-3-319-08016-1_29 |
Published version: | http://dx.doi.org/10.1007/978-3-319-08016-1_29 |
Appears in Collections: | Aurora harvest 2 Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.