
06559780
j
06559780
Jansen, Klaus
Pr\"adel, Lars
New approximability results for twodimensional bin packing.
Algorithmica 74, No. 1, 208269 (2016).
2016
Springer US, New York, NY
EN
bin packing
rectangle packing
approximation algorithms
Zbl 0977.90043
Zbl 0447.68079
doi:10.1007/s004530149943z
The paper studies twodimensional 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.5approximation 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 [{\it C. Kenyon} and {\it E. R\'emila}, Math. Oper. Res. 25, No. 4, 645656 (2000; Zbl 0977.90043)]. The developed algorithm packs rectangles with linear programs and with Next Fit Decreasing Height [{\it E. G. Coffman jun.} et al., SIAM J. Comput. 9, 808826 (1980; Zbl 0447.68079)].
Svetlana A. Kravchenko (Minsk)