An approximation scheme for some Steiner tree problems in the plane

An approximation scheme for some Steiner tree problems in the plane

0.00 Avg rating0 Votes
Article ID: iaor2002390
Country: United States
Volume: 28
Issue: 4
Start Page Number: 187
End Page Number: 193
Publication Date: Dec 1996
Journal: Networks
Authors: ,
Keywords: Steiner problem, minimum spanning trees
Abstract:

We design a polynomial-time approximation scheme for the Steiner tree problem in the plane when the given set of regular points is c-local, i.e., in the minimum-cost spanning tree for the given set of regular points, the length of the longest edge is at most c times the length of the shortest edge. The algorithm works for both Euclidean and rectilinear metrics. For a fixed number k, the performance ratio of our algorithm is 1 + (35c/3k2) for the Euclidean metric and 1 + (9c/k) for the rectilinear metric. Thus, when k increases, the performance ratio approaches 1.

Reviews

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