The Quest for Optimal Solutions for the Art Gallery Problem: A Practical Iterative Algorithm

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.