Abstract
In advice complexity model of online bin packing, suppose there is an offline oracle with infinite computational power. The oracle can provide some information to the online calculation about future items after scanning the whole list of items. This approach can loosen online constraints. The online algorithm receives an advice bit upon the arrival of each item and makes the packing decision. In 2-dimensional online bin packing with advice problem, each item is a rectangle of side lengths less than or equal to 1. The items are to be packed into square bins of size 1×1, without overlapping, allowing 90° rotations. The goal is to pack the items into the minimum number of square bins. In this paper, a 2.25-competitive 2-dimensional online rectangular packing algorithm with three bits of advice per item is presented. Furthermore, an online strategy with competitive ratio 2 requiring three bits of advice per item is given for square packing.
| Original language | English |
|---|---|
| Pages (from-to) | 25-32 |
| Number of pages | 8 |
| Journal | Neurocomputing |
| Volume | 189 |
| DOIs | |
| Publication status | Published - 12 May 2016 |
| Externally published | Yes |
Keywords
- Advice string
- Asymptotic worst case ratio
- Online 2D packing
- Rotatable