In this article, we consider the problem of computing minimum dominating set for a given set @math of @math points in @math . Here the objective is to find a minimum cardinality subset @math of @math such that the union of the unit radius disks centered at the points in @math covers all the points in @math . We first propose a simple 4-factor and 3-factor approximation algorithms in @math and @math time respectively improving time complexities by a factor of @math and @math respectively over the best known result available in the literature [M. De, G.K. Das, P. Carmi and S.C. Nandy, Approximation algorithms for a variant of discrete piercing set problem for unit disk , Int. J. of Comp. Geom. and Appl., to appear]. Finally, we propose a very important shifting lemma, which is of independent interest and using this lemma we propose a @math -factor approximation algorithm and a PTAS for the minimum dominating set problem.
Given a set of n points and a set of m unit disks on a 2-dimensional plane, the discrete unit disk cover (DUDC) problem is (i) to check whether each point in is covered by at least one disk in or not and (ii) if so, then find a minimum cardinality subset such that the unit disks in cover all the points in . The discrete unit disk cover problem is a geometric version of the general set cover problem which is NP-hard. The general set cover problem is not approximable within , for some constant c, but the DUDC problem was shown to admit a constant factor approximation. In this paper, we provide an algorithm with constant approximation factor 18. The running time of the proposed algorithm is . The previous best known tractable solution for the same problem was a 22-factor approximation algorithm with running time . Abstract This is the twelfth edition of a quarterly column that provides continuing coverage of new developments in the theory of NP-completeness. The presentation is modeled on that used by M. R. Garey and myself in our book “Computers and Intractability: A Guide to the Theory of NP-Completeness,” W. H. Freeman & Co., New York 1979 (hereinafter referred to as “[GJ previous columns will be referred to by their dates). A background equivalent to that provided by [G&J] is assumed, and, when appropriate, cross-references will be given to that book and the list of problems (NP-complete and harder) presented there. Readers who have results they would like mentioned (NP-hardness, PSPACE-hardness, polynomial-time-solvability, etc.), or open problems they would like publicized, should send them to David S. Johnson, Room 2C-355, AT&T Bell Laboratories, Murray Hill, NJ 07974 (CSNET address: dsj.rabbit.btl@csnet-relay). Please include details, or at least sketches, of any new proofs (full papers are preferred). If the results are unpublished, please state explicitly that you would like them to be mentioned in the column. Comments and corrections are also welcome. For more details on the nature of the column and the form of desired submissions, see the December 1981 issue of this Journal. We consider the problem of computing minimum geometric hitting sets in which, given a set of geometric objects and a set of points, the goal is to compute the smallest subset of points that hit all geometric objects. The problem is known to be strongly NP-hard even for simple geometric objects like unit disks in the plane. Therefore, unless P = NP, it is not possible to get Fully Polynomial Time Approximation Algorithms (FPTAS) for such problems. We give the first PTAS for this problem when the geometric objects are half-spaces in ℝ3 and when they are an r-admissible set regions in the plane (this includes pseudo-disks as they are 2-admissible). Quite surprisingly, our algorithm is a very simple local-search algorithm which iterates over local improvements only.