Approximation Algorithms for 3D Orthogonal Knapsack

查看全文 作　　者：Florian [1]Diedrich;Rolf [2]Harren;Klaus [1]Jansen;Ralf Th[1]le;Henning [3]Thomas

机构地区：[1]Institute of Computer Science, University of Kiel;[2]Max-Planck-Institut für Informatik,Campus E14,66123 Saarbrücken, Germany;[3]Department of Computer Science, ETH Zurich,Zurich, Switzerland

出　　处：《Journal of Computer Science & Technology》索引2008年第23卷第5期,共14页

基　　金：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 GermanAcademic Exchange Service DAAD. Part of this work was done in duration of visit to the LIG, Grenoble University. 摘　　要：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. 关键词：近似值运算法则复杂性几何构型

相关文献

参考文献（32）
引证文献（0）
耦合文献（1）

参考文献(32)

耦合文献(1)

互联网出版许可证新出网证(渝)字10号全国400电话 - 免长途话费

Approximation Algorithms for 3D Orthogonal Knapsack

参考文献(32)

耦合文献(1)

用户提示