Approximation Algorithms for 3D Orthogonal Knapsack

摘要

We study non-overlapping axis-parallel packings of 3D boxes with profits into a dedicated bigger box where rotation is forbidden; we wish to maximize the total profit. Since this optimization problem is NP-hard, we focus on approximation algorithms. We obtain fast and simple algorithms with approximation ratios 9 + ε and 8 + ε as well as an algorithm with approximation ratio 7 + ε that uses more sophisticated techniques; these are the smallest approximation ratios known for this problem. Topics: Algorithms, computational and structural complexity.