EADS Talk by Arindam Khan: Pseudo-polynomial-time approximation of strip


Pseudo-polynomial-time approximation of strip packing.


Strip packing is a classical packing problem which generalizes both bin packing and makespan minimization. Here we are given a set of axis-parallel rectangles in the two-dimensional plane and the goal is to pack them in a vertical strip of fixed width such that the height of the obtained packing is minimized. The packing must be non-overlapping and the rectangles cannot be rotated. A reduction from the partition problem shows that no approximation better than 3/2 is possible for strip packing in polynomial time (assuming P!=NP). Nadiradze and Wiese [SODA16] overcame this barrier by presenting a (7/5+\epsilon)-approximation algorithm in pseudo-polynomial-time (PPT).

In this talk we will present a (4/3+\epsilon)-approximation algorithm. Our PPT algorithm  can be adapted to the case where we are allowed to rotate the rectangles by 90 degrees, achieving the same approximation factor and breaking the polynomial-time approximation barrier of 3/2 for the case with rotations as well. We will also mention the very recent progress by three other papers on this problem.


Arindam Khan is  a postdoctoral researcher in IDSIA, SUPSI in Lugano, Switzerland. His research areas include approximation algorithms, online algorithms and computational geometry. He has obtained his PhD in Algorithms, Combinatorics and Optimization (ACO) from Georgia Tech, Atlanta under Prof. Prasad Tetali. 

Previously he has been a research intern in Theory group, Microsoft Research, Redmond and Microsoft Research, Silicon Valley and a visiting researcher at Simons Institute, Berkeley, USA.