Improved Approximation Algorithm for Two-Dimensional Bin Packing

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.

Authors

• Nikhil Bansal 0001
• Arindam Khan 0001

Keywords

• Rectangle Packing
• Bin Packing
• Scheduling and Resource Allocation Problems
• Approximation Algorithms
• Combinatorial Optimization