BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/537
DTSTAMP:20230914T125928Z
SUMMARY:Hardness of Vertex Guarding Polygons With Holes
DESCRIPTION:Speaker: Pritam Bhattacharya\n\nAbstract: \nAbstract: The VERTE
 X GUARD (VG) problem is defined as follows: Given a polygon P (with holes 
 allowed) with n vertices\, find a smallest subset S of the set of vertices
  of P such that every point in the polygon P can be seen from at least one
  vertex in S. The vertices in S are called the vertex guards.\n\nIn this t
 alk\, we will prove that VERTEX GUARD is NP-hard by showing a reduction fr
 om SET COVER which was put forward by Eidenbenz\, Stamm and Widmayer in 19
 98. If time permits\, we will also present our own modifications to this r
 eduction that proves that VERTEX GUARD is NP-hard even when considering th
 e special class of polygons with holes that are weakly visible from an edg
 e. In fact\, we can show that there cannot exist a polynomial time algorit
 hm for the vertex guard problem with an approximation ratio better than $(
 (1−\\epsilon)/12)\\ln n$ for any $\\epsilon>0$\, unless NP $\\subseteq$ 
 TIME($n^{\\mathcal{O}(\\log\\log n)}$).\n
URL:https://www.tcs.tifr.res.in/web/events/537
DTSTART;TZID=Asia/Kolkata:20140926T140000
DTEND;TZID=Asia/Kolkata:20140926T153000
LOCATION:D-405 (D-Block Seminar Room)
END:VEVENT
END:VCALENDAR