On Two Dimensional Packing

✍ Scribed by Yossi Azar; Leah Epstein

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 247 KB
• Volume: 25
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1997.0876

✦ Synopsis

The paper considers packing of rectangles into an infinite bin. Similar to the Tetris 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 Ž Ž .. of O log 1r⑀ , where ⑀ is the minimum width of any rectangle. We also show that Ž .

' no algorithm can achieve a better ratio than ⍀ log 1r⑀ for this case.