Seminar

In this talk, we discuss our attempts to solve an important open problem regarding Terrain Guarding: is the state-of-the-art polynomial-time approximation scheme for the problem [Gibson2014], a simple local search construct, optimal? In this regard, we first sketch a proof of a recent advancement in this domain by Mustafa and Jartoux [Jartoux2018]. This work proves, for geometric hitting set problems which give rise to arbitrarily large grid-like exchange graphs, that the local search algorithm is indeed optimal. In light of this result, we question if the Terrain Guarding problem can give rise to such grids. We will conclude the talk by laying out a possible plan for future work on this problem.