BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/640
DTSTAMP:20230914T125932Z
SUMMARY:Approximation Algorithms for Geometric Covering and Packing Problem
 s
DESCRIPTION:Speaker: Rajiv Raman (Indraprastha Institute of Information Tec
 hnology\nOkhla Industrial Estate\nPhase III\n(Near Govind Puri Metro Stati
 on)\nNew Delhi 110020)\n\nAbstract: \nAbstract: In the classic set cover p
 roblem we are given a finite ground set $X$ of elements and a collection o
 f subsets of $X$ whose union covers $X$. The problem is to find a sub-coll
 ection of smallest cardinality from the given collection that still forms 
 a cover of $X$. In the classic packing problem\, we want the largest cardi
 nality sub-collection that are pairwise disjoint. These classic problems a
 re well reasonably well understood in the abstract setting.\n\nIn this tal
 k\, we consider these problems in the geometric setting. Here\, the elemen
 ts of $X$ are points in the plane\, and the subsets of $X$ are defined by 
 geometric regions. These problems are not as well understood in the geomet
 ric setting. For example\, there are gaps between the unweighted setting d
 escribed above\, and the weighted setting in which the sets have weights a
 nd we want to find the minimum (or maximum) weight sub-collection that for
 ms a cover (or forms a packing).\n\nWe present approximation algorithms fo
 r the covering problem where the sets are non-piercing\, i.e.\, for any tw
 o regions simply connected $A$ and $B$\, the regions $AB$ and $BA$ are con
 nected. We extend these results to a related covering problem\, namely the
  dominating set problem as well as a generalization of the packing problem
  where the points (or sets) have capacities that are bounded by a constant
 . The results in this talk were obtained jointly with Aniket Basu\, Sathis
 h Govindarajan\, Nabil Mustafa and Saurabh Ray.\n
URL:https://www.tcs.tifr.res.in/web/events/640
DTSTART;TZID=Asia/Kolkata:20151208T160000
DTEND;TZID=Asia/Kolkata:20151208T170000
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR