Abstract
We study the two-dimensional bin packing problem with and without rotations. Here we are given a set of two-dimensional rectangular items I and the goal is to pack these into a minimum number of unit square bins. We consider the orthogonal packing case where the edges of the items must be aligned parallel to the edges of the bin. Our main result is a 1.405-approximation for two-dimensional bin packing with and without rotation, which improves upon a recent 1.5 approximation due to Jansen and Prädel. We also show that a wide class of rounding based algorithms cannot improve upon the factor of 1.5.
| Original language | English |
|---|---|
| Title of host publication | Proceedings 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'14, Portland OR, USA, January 5-7, 2014) |
| Editors | C. Chekuri |
| Place of Publication | Philadelphia PA |
| Publisher | Society for Industrial and Applied Mathematics (SIAM) |
| Pages | 13-25 |
| ISBN (Print) | 978-1-61197-338-9 |
| DOIs | |
| Publication status | Published - 2014 |
| Event | 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014) - Hilton Portland & Executive Tower, Portland, United States Duration: 5 Jan 2014 → 7 Jan 2014 Conference number: 25 https://www.siam.org/meetings/da14/ |
Conference
| Conference | 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014) |
|---|---|
| Abbreviated title | SODA '14 |
| Country/Territory | United States |
| City | Portland |
| Period | 5/01/14 → 7/01/14 |
| Internet address |