  We present new approximation schemes for bin packing based on the following
two approaches: (1) partitioning the given problem into mostly identical
sub-problems of constant size and then construct a solution by combining the
solutions of these constant size sub-problems obtained through PTAS or exact
methods; (2) solving bin packing using irregular sized bins, a generalization
of bin packing, that facilitates the design of simple and efficient recursive
algorithms that solve a problem in terms of smaller sub-problems such that the
unused space in bins used by an earlier solved sub-problem is available to
subsequently solved sub-problems.
