On Two Dimensional Packing |
| |
Authors: | Yossi Azar Leah Epstein |
| |
Affiliation: | Department of Computer Science, Raymon and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Ramat Aviv, Tel Aviv, 69978, Israel |
| |
Abstract: | The paper considerspacking of rectanglesinto an infinite bin. Similar to theTetris game, the rectangles arrive from the top and, once placed, cannot be moved again. The rectangles are moved inside the bin to reach their place. For the case in which rotations are allowed, we design an algorithm whose performance ratio is constant. In contrast, if rotations are not allowed, we show that no algorithm of constant ratio exists. For this case we design an algorithm with performance ratio ofO(log(1/)), where is the minimum width of any rectangle. We also show that no algorithm can achieve a better ratio thanfor this case. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|