Approximation Algorithms for Multidimensional Packing


Arindam Khan


Technical University
Institute for Informatics
Arcisstraße 21
80333 München


Thursday, 26 April 2018, 10:00 to 11:00


  • A-201 (STCS Seminar Room)


Multidimensional packing problems find numerous applications in robotics, cloud computing, smart-grids and many other scheduling and resource allocation problems. This talk will mainly focus on the two-dimensional geometric knapsack problem (2DK), a geometric variant of the classical knapsack problem. In this problem, we are given a set of axis-aligned rectangular items, each one with an associated profit, and an axis-aligned square knapsack. The goal is to find a (non-overlapping) packing of a maximum profit subset of items inside the knapsack without rotating items. This is a very well studied NP-hard optimization problem and finds applications in scheduling, memory allocation, advertisement placement etc. The best-known polynomial-time approximation factor for this problem (even just in the cardinality case) is (2+\epsilon) by [Jansen and Zhang, SODA 2004]. After more than a decade, by introducing new algorithmic techniques, we break the 2-approximation barrier, achieving a polynomial-time  (17/9+\epsilon) <1.89-approximation.

This result appeared in FOCS 2017.  This is a joint work with Waldo Galvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala and Andreas Wiese. The talk will also briefly mention some related problems (such as vector packing and geometric bin packing) and other general research areas of the speaker.

Bio: Arindam Khan is a postdoctoral researcher in TU Munich, Germany. His research areas include approximation algorithms, online algorithms, and computational geometry. He has obtained his Ph.D. in Algorithms, Combinatorics and Optimization (ACO) from Georgia Institute of Technology, Atlanta, USA under Prof. Prasad Tetali.  Previously he has been a research intern in Theory group, Microsoft Research Redmond and Microsoft Research Silicon Valley USA; a visiting researcher at Simons Institute, University of California, Berkeley, USA; a blue scholar in IBM Research India; and a researcher in IDSIA, Lugano, Switzerland.