ANALYSIS OF GREEDY ALGORITHM FOR DOMINATING SET PROBLEM ON ANCHORED RECTANGLES

Abstract

We are given a set R of n Axis-Parallel Rectangles in the plane. We study the Dominating set problem on R. The bottom left vertex of each rectangle in set R is constrained to touch a straight diagonal line of 135 . We study the performance of greedy algorithm for Minimum Dominating set (MDS) problem on the Intersection Graph of R. We give a construction, on R, where Greedy technique yields (log n)-factor approximation. This proves that the approximation ratio for Greedy algorithm for MDS problem is (log n) even for this constrained version of MDS problem. We also do an experimental study of Greedy algorithm of MDS problem for randomly generated arbitrary rectangles. We compare the performance of greedy algorithm with optimal result obtained by solving Integer Linear program- ming (ILP) formulation of MDS problem.