Approximations for a bottleneck Steiner tree problem

Approximations for a bottleneck Steiner tree problem

0.00 Avg rating0 Votes
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: ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.