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