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