Approximation Algorithm for Bottleneck Steiner Tree Problem in the Euclidean Plane

A special case of thebottleneck Steiner tree problem in the Euclidean plane was considered in this paper. The problem has applications in the design of wireless communication networks, multifacility location, VLSI routing and network routing. For the special case which requires that there should be no edge connecting any two Steiner points in the optimal solution, a 3-restricted Steiner tree can be found indicating the existence of the performance ratio √2. In this paper, the special case of the problem is proved to beNP-hard and cannot be approximated within ratio √2. First a simple polynomial time approximation algorithm with performance ratio √2 is presented. Then based on this algorithm and the existence of the 3-restricted Steiner tree, a polynomial time approximation algorithm with performance ratio—√2+∈ is proposed, for any ∈>0. Supported partially by Shandong Province Excellent Middle-Aged and Young Scientists Encouragement Fund (Grant No.03BS004) and the Ministry of Education Study Abroad Returnees Research Start-up Fund, and the National Natural Science Foundation of China (Grant No.60273032).