Talks & Seminars
Title: Approximating Geometric Knapsack via L-packings
Dr. Arindam Khan, IDSIA, SUPSI in Lugano, Switzerland
Date & Time: August 23, 2017 11:30
Venue: Conference Room, 01st Floor, C Block, Department of Computer Science and Engineering, Kanwal Rekhi (KReSIT) Building
We study 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 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+\eps$ [Jansen and Zhang, SODA 2004]. After more than a decade, in this paper we break the 2-approximation barrier, achieving a polynomial-time 17/9+\eps (which is less than 1.89) approximation, which improves to 558/325+\eps (i.e 1.72) in the cardinality case. We also consider the variant of the problem with rotations (2DKR) , where the items can be rotated by 90 degrees. Also in this case the best-known polynomial-time approximation factor (even for the cardinality case) is 2+\eps [Jansen and Zhang, SODA 2004]. Exploiting part of the machinery developed for 2DK plus a few additional ideas, we obtain a polynomial-time 3/2+\eps-approximation for 2DKR, which improves to 4/3+\eps in the cardinality case. This is a joint work with Waldo Galvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala and Andreas Wiese. This result will appear in FOCS 2017.
Speaker Profile:
Arindam Khan is a 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 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, Berkeley, USA and a blue scholar in IBM Research India.
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback