BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/108
DTSTAMP:20230914T125910Z
SUMMARY:Local Search for Geometric Set Cover Problems
DESCRIPTION:Speaker: Kasturi Varadarajan\nUniversity of Iowa\nDepartment of
Computer Science\nIowa City\, IA 52242-1419\nUnited States\n\nAbstract: \
nIn SocG 2009\, Mustafa and Ray showed that a local search algorithm is\,
somewhat surprisingly\, a PTAS for certain geometric set cover/hitting set
problems. In this context\, a PTAS is a scheme that for any eps > 0\, yie
lds an algorithm that runs in polynomial time and returns a solution whose
size is at most (1 + eps) times that of the optimal set cover/hitting set
. A similar PTAS was presented by Chan and Har-Peled at the same conferenc
e for the largest independent set problem in certain geometric intersectio
n graphs.\n\nWe will discuss a hitting set result of Mustafa and Ray and\,
time permitting\, an application of their machinery to a terrain guarding
problem by Gibson\, Kanade\, Krohn\, and the speaker.\n
URL:https://www.tcs.tifr.res.in/web/events/108
DTSTART;VALUE=DATE:20100728
LOCATION:D-405
END:VEVENT
END:VCALENDAR