Online algorithms for 2D bin packing with advice

Xiaofan Zhao, Hong Shen

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


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 languageEnglish
Pages (from-to)25-32
Number of pages8
Publication statusPublished - 12 May 2016
Externally publishedYes


  • Advice string
  • Asymptotic worst case ratio
  • Online 2D packing
  • Rotatable


Dive into the research topics of 'Online algorithms for 2D bin packing with advice'. Together they form a unique fingerprint.

Cite this