Tata Institute of Fundamental Research
The Quest for Optimal Solutions for the Art Gallery Problem: A Practical Iterative Algorithm
STCS Student Seminar
Speaker:
Pritam Bhattacharya (Indian Institute of Technology
Department of Computer Science
and Engineering
Kharagpur 721302
)
Organiser:
Phani Raj Lolakapuri
Date:
Friday, 17 Jun 2016, 16:00 to 17:30
Venue:
AG-80
(Scan to add to calendar)
Abstract:
The 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 problem 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 lower bounds while seeking to reach an exact solution. Though there have been some notable approximation algorithms for solving particular variants of AGP (such as those by Ghosh; Deshpande et al; King and Kirkpatrick; Nilsson et al; Bhattacharya et al), this is the first exact algorithm that has been proposed for this problem.
The 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 bounds are computed iteratively from the linear programming relaxation of the SCP formulation. Then, the solutions of the primal and dual linear programs are used to guide the refinement of the witness and the guard candidate sets, giving rise to larger models, in an attempt to continuously reduce the duality gap. Whenever convergence happens and integrality of the primal linear relaxation variables is obtained, an optimal solution is found.
| Speaker: | Pritam Bhattacharya (Indian Institute of Technology Department of Computer Science and Engineering Kharagpur 721302 ) |
| Organiser: | Phani Raj Lolakapuri |
| Date: | Friday, 17 Jun 2016, 16:00 to 17:30 |
| Venue: | AG-80 |
(Scan to add to calendar)
Abstract:
The 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 problem 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 lower bounds while seeking to reach an exact solution. Though there have been some notable approximation algorithms for solving particular variants of AGP (such as those by Ghosh; Deshpande et al; King and Kirkpatrick; Nilsson et al; Bhattacharya et al), this is the first exact algorithm that has been proposed for this problem.
The 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 bounds are computed iteratively from the linear programming relaxation of the SCP formulation. Then, the solutions of the primal and dual linear programs are used to guide the refinement of the witness and the guard candidate sets, giving rise to larger models, in an attempt to continuously reduce the duality gap. Whenever convergence happens and integrality of the primal linear relaxation variables is obtained, an optimal solution is found.
The 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 bounds are computed iteratively from the linear programming relaxation of the SCP formulation. Then, the solutions of the primal and dual linear programs are used to guide the refinement of the witness and the guard candidate sets, giving rise to larger models, in an attempt to continuously reduce the duality gap. Whenever convergence happens and integrality of the primal linear relaxation variables is obtained, an optimal solution is found.