Approximation Algorithms for 3D Orthogonal KnapsackReport as inadecuate

Approximation Algorithms for 3D Orthogonal Knapsack - Download this document for free, or read online. Document in PDF available to download.

Journal of Computer Science and Technology

, 23:749

First Online: 03 November 2008Revised: 10 July 2008


We study non-overlapping axis-parallel packings of 3D boxes with profits into a dedicated bigger box where rotation is either forbidden or permitted, and 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 for the non-rotational scenario 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. Furthermore, we show how the used techniques can be adapted to the case where rotation by 90° either around the z-axis or around all axes is permitted, where we obtain algorithms with approximation ratios 6 + ϵ and 5 + ϵ, respectively. Finally our methods yield a 3D generalization of a packability criterion and a strip packing algorithm with absolute approximation ratio 29-4, improving the previously best known result of 45-4.

Keywordsapproximation algorithm computational and structural complexity geometric configurations 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, under EU Contract No. 015964, and in part by a Grant -DAAD Doktorandenstipendium- of the German Academic Exchange Service DAAD. Part of this work was done in duration of visit to the LIG, Grenoble University.

Download to read the full article text

Author: Florian Diedrich - Rolf Harren - Klaus Jansen - Ralf Thöle - Henning Thomas



Related documents