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
| 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
After more than a decade, in this paper we break the 2-approximation barrier, achieving a polynomial-time $17/9+\epsilon