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