Online Bin Packing with Advice of Small Size - Sorbonne Université Accéder directement au contenu
Communication Dans Un Congrès Année : 2015

Online Bin Packing with Advice of Small Size

Spyros Angelopoulos
Christoph Dürr
Shahin Kamali
  • Fonction : Auteur

Résumé

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.
Fichier non déposé

Dates et versions

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

Identifiants

Citer

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 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More