BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/804
DTSTAMP:20230914T125939Z
SUMMARY:Approximating Geometric Knapsack via L-packings
DESCRIPTION:Speaker: Arindam Khan (IDSIA\, SUPSI\nGalleria 2\nVia Cantonale
2c\nCH-6928 Manno TI\nSwitzerland)\n\nAbstract: \nWe study the two-dimens
ional geometric knapsack problem (2DK)\, a geometric variant of the classi
cal knapsack problem. In this problem we are given a set of axis-aligned r
ectangular items\, each one with an associated profit\, and an axis-aligne
d square knapsack. The goal is to find a (non-overlapping) packing of a ma
ximum profit subset of items inside the knapsack without rotating items. T
his is a very well-studied optimization problem and finds applications in
scheduling\, memory allocation\, advertisement placement etc. The best-kno
wn polynomial-time approximation factor for this problem (even just in the
cardinality case) is $2+\\epsilon$ [Jansen and Zhang\, SODA 2004].\n\nAft
er more than a decade\, in this paper we break the 2-approximation barrier
\, achieving a polynomial-time $17/9+\\epsilon\n
URL:https://www.tcs.tifr.res.in/web/events/804
DTSTART;TZID=Asia/Kolkata:20170824T160000
DTEND;TZID=Asia/Kolkata:20170824T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR