New approximability results for two-dimensional bin packing (Q261358)

The paper studies two-dimensional bin packing problems with or without rotations, where a set of rectangles has to be packed into the minimum number of unit squares. The authors develop a polynomial 1.5-approximation algorithm that improves the former best asymptotic approximation ratio and reduces the gap between the known upper and lower bounds. A deep structural analysis of an arbitrary solution is given and it is shown how to round up the sizes of the rectangles to obtain a much more simple solution. The authors use the rounding technique similar to [\textit{C. Kenyon} and \textit{E. Rémila}, Math. Oper. Res. 25, No. 4, 645--656 (2000; Zbl 0977.90043)]. The developed algorithm packs rectangles with linear programs and with Next Fit Decreasing Height [\textit{E. G. Coffman jun.} et al., SIAM J. Comput. 9, 808--826 (1980; Zbl 0447.68079)].