Tata Institute of Fundamental Research

Approximation Algorithms for Multidimensional Packing

STCS Seminar
Speaker: Arindam Khan (Technical University Institute for Informatics Arcisstraße 21 80333 München Germany)
Organiser: Umang Bhaskar
Date: Thursday, 26 Apr 2018, 10:00 to 11:00
Venue: A-201 (STCS Seminar Room)

(Scan to add to calendar)
Abstract:  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)