The classical Art Gallery Problem asks for the minimum number of
guards that achieve visibility coverage of a given polygon. This
problem is known to be NP-hard, even for very restricted and
discrete special cases.
We present a primal-dual algorithm based on linear programming that
provides lower bounds on the necessary number of guards in every
step and---in case of convergence and integrality---ends with an
optimal solution.
In addition, we consider the Art Gallery Problem variant where a polygonal
region is to be covered with light sources that emit light fading with
distance. We describe a practical approximation algorithm based on the simplex
method and primal-dual LP separation. For the case where the light
positions are given, we describe a fully polynomial-time approximation scheme.
We will also consider the possibility of steering towards integer solutions,
e.g., by using cutting planes based on Edge Cover and Set Cover inequalities
to eliminate fractional solutions.