Approximation Algorithms for 3D Orthogonal Knapsack

We study non-overlapping axis-parallel packings of 3D boxes with profitsinto a dedicated bigger box where rotation is either forbidden orpermitted, and we wish to maximize the total profit. Since thisoptimization problem is NP-hard, we focus on approximation algorithms.We obtain fast and simple algorithms for the non-rotational scenariowith approximation ratios 9+ and 8+, as well as analgorithm with approximation ratio 7+ that uses moresophisticated techniques; these are the smallest approximation ratiosknown for this problem. Furthermore, we show how the used techniques canbe adapted to the case where rotation by 90° either around thez-axis or around all axes is permitted, where we obtain algorithmswith approximation ratios 6+ and 5+, respectively.Finally our methods yield a 3D generalization of a packability criterionand a strip packing algorithm with absolute approximation ratio 29/4,improving the previously best known result of 45/4.