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 shortest k-edge-connected spanning network on P, and let r_k = inf{l_k(P)|P} for k ≥ 1. In this paper, we show that in any metric space, r_k ≥ 3/4 for k ≥ 2, and there exists a polynomial-time α-approximation for the shortest k-edge-connected Steiner network, where α = 2 for even k and α = 2 + 4/(3k) for odd k. In the Euclidean plane, r_k ≥ √3/2, r3 ≤ (√3+2)/4 and r₄ ≤ (7+3√3)/(9+2√3).