Inapproximability of Euclidean Steiner TreeResearch Paper
The Euclidean Steiner Tree problem asks for a shortest network connecting given points (terminals) in , where additional Steiner points may be placed anywhere. It goes back to the Fermat–Torricelli problem, and it is NP-hard already in the plane (Garey, Graham and Johnson, 1977). In fixed dimension it admits a polynomial-time approximation…