%0 Journal Article
%T Approximation Algorithms for 3D Orthogonal Knapsack
%A Florian Diedrich
%A Rolf Harren
%A Klaus Jansen
%A Ralf Th?le
%A Henning Thomas
%A <br>Florian Diedrich
%A Rolf Harren
%A Klaus Jansen
%A Ralf Th
%A le
%A and Henning Thomas
%J 计算机科学技术学报
%D 2008
%I 
%X 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. 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.
%K approximation algorithm
%K computational and structural complexity
%K geometric configurations<br>
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=F57FEF5FAEE544283F43708D560ABF1B&aid=393044A7BF9ABEB15167B0782AC64FEA&yid=67289AFF6305E306&vid=EA389574707BDED3&iid=94C357A881DFC066&sid=762CFFBBDED11937&eid=1CBB73E9593E8833&journal_id=1000-9000&journal_name=计算机科学技术学报&referenced_num=0&reference_num=32