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 pro...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.展开更多
基金supported in part by DFG Project,Entwicklung und Analyse von Approximativen Algorithmen für Gemischte und Verallgemeinerte Packungs-undüberdeckungsprobleme,JA 612/10-1in part by the German Academic Exchange Service DAAD+2 种基金in part by project AEOLUS,under EU Contract No.015964in part by a Grant"DAAD Doktorandenstipendium"of the GermanAcademic Exchange Service DAADPart 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.
