Nearly optimal solution for restricted euclidean bottleneck Steiner tree problem

A variation of the traditional Steiner tree problem, the bottleneck Steiner tree problem is considered in this paper, which asks to find a Steiner tree for n terminals with at most k Steiner points such that the length of the longest edge in the tree is minimized. The problem has applications in the design of WDM optical networks, design of wireless communication networks and reconstruction of phylogenetic tree in biology. We study a restricted version of the bottleneck Steiner tree problem in the Euclidean plane which requires that only degree-2 Steiner points are possibly adjacent in the optimal solution. The problem is known to be MAX-SNP hard and cannot be approximated within 2 unless P=NP, we propose a nearly optimal randomized polynomial time approximation algorithm with performance ratio 2+ε, where ε is a positive number. © 2014 ACADEMY PUBLISHER.