On-line algorithms for 2-space bounded 2-dimensional bin packing

In 2-space bounded model of on-line bin packing, there are 2 active bins, and each item can be packed only into one of the 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 2-space bounded 2-dimensional bin packing problem, each item is a rectangle of side lengths not greater than 1. The items are packed on-line into square bins of size 1×1 and 90°-rotations are allowed. In this paper a 4-competitive 2-space bounded 2-dimensional on-line packing algorithm is presented. Furthermore, an on-line strategy with competitive ratio 3.8 is given for 2-space bounded square packing.