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