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.
