We consider 2Dimensional (Finite) Bin Packing (\FBP), which is one of
the most important generalizations of the wellknown 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 \FBP,
whereas the situation for the {\em 2stage} case, in which the items
must first be packed into {\em shelves} that are then packed into
bins, is essentially settled. For this reason, we study the asymptotic
worstcase ratio between the optimal solution values of the 2stage
and general \FBP, showing that it is equal to $\Tinf=1.691\ldots$, the
wellknown worstcase ratio of the {\em 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 \FBP\ whose asymptotic worstcase ratio
is arbitrarily close to $\Tinf$, i.e.\ substantially smaller than
$2+\eps$, 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
standalone 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 worstcase ratio of several shelf heuristics for \FBP,
among which a bound of $(\frac{17}{10})(\frac{11}{9})=2.077\ldots$
(rather than $2.125$) on the 20yearslasting champion mentioned
above. Moreover, we can easily derive the asymptotic worstcase ratio
between the 2stage and general \FBP\ solution values as a function of
the maximum width of the rectangles, showing that this ratio is
independent of the maximum height.
