Approximation Algorithm for Bottleneck Steiner Tree Problem in the Euclidean Plane

Abstract
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 3restrictedSteiner tree can be found indicating the existence of theperformance ratio sqrt(2). In this paper, the special case of the problem is provedto be NPhard 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 3restricted Steiner tree, a polynomial timeapproximation algorithm with performance ratiosqrt(2)+epsilonis proposed, for any epsilon > 0 .

