On shortest k-edge-connected Steiner networks in metric spaces

Given a set of points P in a metric space, let l(k)(P) denote the ratio of lengths between the shortest k-edge-connected Steiner network and the short est k-edge-connected spanning network on P, and let r(k) = inf{l(k)(P) \ P} for k greater than or equal to 1. In this paper, we show that in any metri c space, r(k) greater than or equal to 3/4 for k greater than or equal to 2 , and there exists a polynomial-time alpha-approximation for the shortest k -edge-connected Steiner network, where alpha = 2 for even k and alpha = 2 4/(3k) for odd k. In the Euclidean plane, r(k) greater than or equal to ro ot 3/2, r(3) less than or equal to (root 3+2)/4 and r(4) less than or equal to (7+3 root 3)/(9+2 root 3).