Improved Approximation Algorithms for Three-Dimensional Bin Packing

Abstract

We study two fundamental three-dimensional (3D) geometric packing problems: 3D (Geometric) Bin Packing (3D-BP), and 3D Minimum Volume Bounding Box (3D-MVBB), where given a set of 3D (rectangular) cuboids, the goal is to find an axis-aligned nonoverlapping packing of all cuboids. In 3D-BP, we need to pack the given cuboids into the minimum number of unit cube bins. In 3D-MVBB, the goal is to pack them into a cuboid box of minimum volume. It is NP-hard to even decide whether a set of rectangles can be packed into a unit square bin -- giving an (absolute) approximation hardness of $2$ for 3D-BP. The previous best (absolute) approximation for both the problems follows from a result of Buchwald and Scheithauer (Int.~Trans.~Oper.~Res., 2016), yielding approximation ratios of $11$, and $5+\epsilon$, respectively, for 3D-BP and 3D-MVBB. We provide improved approximation ratios of $6$, and $3+\epsilon$, respectively, for the two problems, for any constant $\epsilon >0$. For 3D-BP, in the asymptotic regime, Bansal, Correa, Kenyon, and Sviridenko (Math.~Oper.~Res., 2006) showed that there is no asymptotic polynomial-time approximation scheme (APTAS) even when all items have the same height. Caprara (Math.~Oper.~Res., 2008) gave an asymptotic approximation ratio of $T_{\infty }^2+\epsilon \approx 2.86$, where $T_{\infty }$ is the well-known Harmonic constant in Bin Packing. We provide an algorithm with an improved asymptotic approximation ratio of $3T_{\infty }/2+\epsilon \approx 2.54$. Further, we show that unlike 3D-BP, 3D-MVBB admits an APTAS.