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.
Research supported in part by DFG Project, “Entwicklung und Analyse von Approximativen Algorithmen für Gemischte und Verallgemeinerte
Packungs- und Überdeckungsprobleme, JA 612/10-1”, in part by the German Academic Exchange Service DAAD, in part by project
AEOLUS, EU contract number 015964, and in part by a grant “DAAD Doktorandenstipendium” of the German Academic Exchange Service
DAAD. Part of this work was done while visiting the ID-IMAG, ENSIMAG, Grenoble.