# Kolloquiumsvortrag (INF) Arindam Khan, TU München / am 02.02.2018

02.02.2018 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Straße 2, 24118 Kiel, Raum: Übungsraum 2/K

Titel: Approximating Geometric Knapsack via L-packings

Abstract: 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+\epsilon$ [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+\epsilon<1.89$ approximation,
which improves to $558/325+\epsilon<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+\epsilon$ [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+\epsilon$-approximation for
2DKR, which improves to $4/3+\epsilon$ in the cardinality case (joint
work with Waldo Galvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore
Ingala and Andreas Wiese.).

Bio: Arindam Khan is a postdoc in Lehrstuhl für Theoretische Informatik
at Technische Universität München. 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; a blue scholar
in IBM Research India and a researcher at IDSIA, Lugano, Switzerland.