Tata Institute of Fundamental Research

Approximating Geometric Knapsack via L-packings

STCS Seminar
Speaker: Arindam Khan (IDSIA, SUPSI Galleria 2 Via Cantonale 2c CH-6928 Manno TI Switzerland)
Organiser: Jaikumar Radhakrishnan
Date: Thursday, 24 Aug 2017, 16:00 to 17:00
Venue: A-201 (STCS Seminar Room)

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