Harmonic algorithm for 3-dimensional strip packing problem

Abstract

In the three dimensional strip packing problem, we are given a set of three-dimensional rectangular items I = {f(xi, yi, zi) : i = 1, ⋯, n} and a three dimensional box B. The goal is to pack all the items in the box B without any overlap, such that the height of the packing is minimized. We consider the most basic version of the problem, where the items must be packed with their edges parallel to the edges of B and cannot be rotated. Building upon Caprara's work [4] for the two dimensional bin packing problem we obtain an approximation algorithm with a similar performance guarantee of T∞ ≊ 1.69 where T∞ is the well known Harmonic number that occurs naturally in the context of bin packing. The previously known approximation algorithms for this problem had worst case performance guarantees of 2 [7], 2.64 [14], 2.67 [15], 2.89 [10] and 3.25 [11]. Our second algorithm is an asymptotic PTAS for the case in which all items have square bases.