Packing 2-dimensional bins in harmony

We consider 2-Dimensional (Finite) Bin Packing (2BP), which is one of the most important generalizations of the well-known Bin Packing (BP) and calls for orthogonally packing a given set of rectangles (that cannot be rotated) into the minimum number of unit size squares. There are many open questions concerning the approximability of 2BP, whereas the situation for the 2-stage case, in which the items must first be packed into shelves that are then packed into bins, is essentially settled. For this reason, we study the asymptotic worst-case ratio between the optimal solution values of the 2-stage and general 2BP, showing that it is equal to T_∞=1.691..., the well-known worst-case ratio of the Harmonic algorithm for BP. This ratio is achieved by packing the items into shelves by decreasing heights as in the Harmonic algorithm and then optimally packing the resulting shelves into bins. This immediately yields polynomial time approximation algorithms for 2BP whose asymptotic worst-case ratio is arbitrarily close to T_∞, i.e. substantially smaller than 2+ε, that was the best ratio achievable so far and constituted the first (recent) improvement over the 2.125 ratio shown in the early 80s. In particular, we manage to push the approximability threshold below 2, which is often a critical value in approximation. The main idea in our analysis is to use the fact that the fractional and integer BP solutions have almost the same value, which is implicit in the approximation schemes for the problem, as a stand-alone structural result. This implies the existence of modified heights for the shelves whose sum yields approximately the number of bins needed to pack them. With this in mind, our proof can easily be adapted to different cases. For instance, we can derive new upper bounds on the worst-case ratio of several shelf heuristics for 2BP, among which a bound of (17/10)(11/9)=2.077... (rather than 2.125) on the 20-years-lasting champion mentioned above. Moreover, we can easily derive the asymptotic worst-case ratio between the 2-stage and general 2BP solution values as a function of the maximum width of the rectangles, showing that this ratio is independent of the maximum height. Finally, under a conjecture that appears to be supporte- d by experimental evidence, we show that our main heuristic has an asymptotic worst-case ratio in the interval (1.490,1.507) when all the rectangles to be packed are squares. This would improve the current best worst-case ratio of 14/9=1.555... for this special case.