BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/869
DTSTAMP:20230914T125941Z
SUMMARY:Approximation Algorithms for Multidimensional Packing
DESCRIPTION:Speaker: Arindam Khan (Technical University\nInstitute for Info
rmatics\nArcisstraße 21\n80333 München\nGermany)\n\nAbstract: \nMultidim
ensional packing problems find numerous applications in robotics\, cloud c
omputing\, smart-grids and many other scheduling and resource allocation p
roblems. This talk will mainly focus on the two-dimensional geometric knap
sack 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 subse
t 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 polynom
ial-time approximation factor for this problem (even just in the cardinali
ty case) is (2+\\epsilon) by [Jansen and Zhang\, SODA 2004]. After more th
an a decade\, by introducing new algorithmic techniques\, we break the 2-a
pproximation barrier\, achieving a polynomial-time (17/9+\\epsilon)\n
URL:https://www.tcs.tifr.res.in/web/events/869
DTSTART;TZID=Asia/Kolkata:20180426T100000
DTEND;TZID=Asia/Kolkata:20180426T110000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR