BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/693
DTSTAMP:20230914T125934Z
SUMMARY:The Quest for Optimal Solutions for the Art Gallery Problem: A Prac
 tical Iterative Algorithm
DESCRIPTION:Speaker: Pritam Bhattacharya (Indian Institute of Technology\nD
 epartment of Computer Science\nand Engineering\nKharagpur 721302\n\n )\n\
 nAbstract: \nThe general Art Gallery Problem (AGP) consists in finding the
  minimum number of guards sufficient to ensure the visibility coverage of 
 an art gallery represented by a polygon. The AGP is a well known NP-hard p
 roblem and\, for this reason\, all algorithms proposed so far to solve it 
 are unable to guarantee optimality\, except in special cases. In this talk
 \, I will present a new method (due to Tozoni\, de Rezende\, and de Souza)
  for solving the Art Gallery Problem by iteratively generating upper and l
 ower bounds while seeking to reach an exact solution. Though there have be
 en some notable approximation algorithms for solving particular variants o
 f AGP (such as those by Ghosh\; Deshpande et al\; King and Kirkpatrick\; N
 ilsson et al\; Bhattacharya et al)\, this is the first exact algorithm 
 that has been proposed for this problem.\n\nThe idea of the new algorithm 
 is to discretize both the witness set and the guard set\, and to model the
  restricted AGP as a Set Cover Problem (SCP). Firstly\, lower and upper b
 ounds are computed iteratively from the linear programming relaxation of t
 he SCP formulation. Then\, the solutions of the primal and dual linear pro
 grams are used to guide the refinement of the witness and the guard candid
 ate sets\, giving rise to larger models\, in an attempt to continuously re
 duce the duality gap. Whenever convergence happens and integrality of the 
 primal linear relaxation variables is obtained\, an optimal solution is fo
 und.\n \n
URL:https://www.tcs.tifr.res.in/web/events/693
DTSTART;TZID=Asia/Kolkata:20160617T160000
DTEND;TZID=Asia/Kolkata:20160617T173000
LOCATION:AG-80
END:VEVENT
END:VCALENDAR