Geometric Dominating Set and Set Cover via Local Search

In this paper, we study two classic optimization problems: minimum geometric dominating set and set cover. In the dominating-set problem, for a given set of objects in the plane as input, the objective is to choose a minimum number of input objects such that every input object is dominated by the chosen set of objects. Here, one object is dominated by another if both of them have a nonempty intersection region. For the second problem, for a given set of points and objects in a plane, the objective is to choose a minimum number of objects to cover all the points. This is a special version of the set-cover problem. For both problems obtaining a PTAS remains open for a large class of objects. For the dominating-set problem, we prove that a popular local-search algorithm leads to an (1+varepsilon) approximation for object sets consisting of homothetic set of convex objects (which includes arbitrary squares, k-regular polygons, translated and scaled copies of a convex set, etc.) in nO(1/varepsilon2) time. On the other hand, the same technique leads to a PTAS for geometric covering problem when the objects are convex pseudodisks (which includes disks, unit height rectangles, homothetic convex objects, etc.). As a consequence, we obtain an easy to implement approximation algorithm for both problems for a large class of objects, significantly improving the best known approximation guarantees.