Online Algorithms for 3-Space Bounded 2-Dimensional Bin Packing and Square Packing

In 2-dimensional bin packing problem each item is a rectangle of side lengths not greater than 1. The items are packed online into square bins of size 1 x 1 and 90 degrees-rotations are allowed. In t-space bounded model of online bin packing each item can be packed only into one of t active bins. If it is impossible to pack an item into any active bin, we close one of the current active bins and open a new active bin to pack that item. In this paper a 3.577-competitive 3-space bounded online packing algorithm is presented. Furthermore, an online algorithm for packing squares with the competitive ratio 2.8 is described.