Name
Title | ||
|---|---|---|
Approximation Algorithms For A Variant Of Discrete Piercing Set Problem For Unit Disks |
Abstract | ||
|---|---|---|
In this paper, we consider constant factor approximation algorithms for a variant of the discrete piercing set problem for unit disks. Here a set of points P is given; the objective is to choose minimum number of points in P to pierce the unit disks centered at all the points in P. We first propose a very simple algorithm that produces 12-approximation result in O(n log n)time. Next, we improve the approximation factor to 4 and then to 3. The worst case running time of these algorithms are O(n(8) log n) and O(n(15) log n) respectively. A part from the space required for storing the input, the extra work-space requirement for each of these algorithms is O(1). Finally, we propose a PTAS for the same problem. Given a positive integer k, it can produce a solution with performance ratio (1+1/k)(2) in n(O(k)) time |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1142/S021819591350009X | INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS |
Keywords | DocType | Volume |
Piercing, minimum dominating set, unit disk, approximation algorithm | Journal | 23 |
Issue | ISSN | Citations |
6 | 0218-1959 | 6 |
PageRank | References | Authors |
0.49 | 17 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Minati De | 1 | 45 | 10.11 |
| Gautam Das | 2 | 4083 | 335.74 |
| Paz Carmi | 3 | 8 | 1.23 |
| Subhas C. Nandy | 4 | 285 | 49.55 |