Article ID: | iaor2012920 |
Volume: | 15 |
Issue: | 1 |
Start Page Number: | 63 |
End Page Number: | 75 |
Publication Date: | Feb 2012 |
Journal: | Journal of Scheduling |
Authors: | Stee Rob, Harren Rolf |
Keywords: | bin packing |
We consider the problem of packing rectangles into bins that are unit squares, where the goal is to minimize the number of bins used. All rectangles have to be packed non‐overlapping and orthogonal, i.e., axis‐parallel. We present an algorithm with an absolute worst‐case ratio of 2 for the case where the rectangles can be rotated by 90 degrees. This is optimal provided