Article ID: | iaor20032945 |
Country: | United States |
Volume: | 32 |
Issue: | 4 |
Start Page Number: | 554 |
End Page Number: | 561 |
Publication Date: | Apr 2002 |
Journal: | Algorithmica |
Authors: | Wang L., Du D.Z. |
In the design of wireless communication networks, due to a budget limit, suppose we could put totally n + k stations in the plane. However, n of them must be located at given point. Of course, one would like to have the distance between stations as small as possible. The problem is how to choose locations for other k stations to minimize the longest distance between stations. This problem is NP-hard. We show that if NP not equal to P, no polynomial-time approximation for the problem in the rectilinear plane has a performance ratio less than 2 and no polynomial-time approximation for the problem in the Euclidean plane has a performance ratio less than root2 and that there exists a polynomial-time approximation with performance ratio 2 for the problem in both the rectilinear plane and the Euclidean plane.