Online Bin Packing with Advice of Small Size - Sorbonne Université Access content directly
Conference Papers Year : 2015

Online Bin Packing with Advice of Small Size

Spyros Angelopoulos
Christoph Dürr
Shahin Kamali
  • Function : Author

Abstract

In this paper, we study the advice complexity of the online bin packing problem. In this well-studied setting, the online algorithm is supplemented with some additional information concerning the input. We improve upon both known upper and lower bounds of online algorithms for this problem. On the positive side, we first provide a relatively simple algorithm that achieves a competitive ratio arbitrarily close to 1.5, using constant-size advice. Our result implies that 16 bits of advice suffice to obtain a competitive ratio better than any online algorithm without advice, thus improving the previously known bound of O(log(n)) bits required to attain this performance. In addition, we introduce a more complex algorithm that still requires only constant-size advice, and which is below 1.5-competitive, namely has competitive ratio arbitrarily close to 1.47012. This is the currently best performance of any online bin packing algorithm with sublinear advice. On the negative side, we extend a construction due to Boyar et al. [10] so as to show that no online algorithm with sub-linear advice can be 7/6-competitive, which improves upon the known lower bound of 9/8.
No file

Dates and versions

hal-01196948 , version 1 (10-09-2015)

Identifiers

Cite

Spyros Angelopoulos, Christoph Dürr, Shahin Kamali, Marc Renault, Adi Rosén. Online Bin Packing with Advice of Small Size. Algorithms and Data Structures, Aug 2015, Victoria, Canada. pp.40-53, ⟨10.1007/978-3-319-21840-3_4⟩. ⟨hal-01196948⟩
195 View
0 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More