Approximation Algorithm for Bottleneck Steiner Tree Problem in the Euclidean Plane

A special case of the bottleneck Steiner tree problem in theEuclidean plane was considered in this paper. The problem hasapplications in the design of wireless communication networks,multifacility location, VLSI routing and network routing. For thespecial case which requires that there should be no edge connecting anytwo Steiner points in the optimal solution, a 3-restrictedSteiner tree can be found indicating the existence of theperformance ratio sqrt(2). In this paper, the special case of the problem is provedto be NP-hard and cannot be approximated within ratio sqrt(2). Firsta simple polynomial time approximation algorithm with performanceratio sqrt(3) is presented. Then based on this algorithm and theexistence of the 3-restricted Steiner tree, a polynomial timeapproximation algorithm with performance ratio---sqrt(2)+epsilonis proposed, for any epsilon > 0 .