On Minimum-Weight k-Edge Connected Steiner Networks on Metric Spaces

Abstract.

For a given set of points P in a metric space, let w _k(P) denote the weight of minimum-weight k-edge connected Steiner network on P divided by the weight of minimum-weight k-edge connected spanning network on P, and let r _k=inf{w _k(P) |P}. We show in this paper that for any P, , for even k≥2 and , for odd k≥3. In particular, we prove that for any P in the Euclidean plane, w ₄(P) and w ₅(P) are greater than or equal to , and ; For any P in the rectilinear plane , for odd k≥5. In addition, we prove that there exists an O(|P|³)-time approximation algorithm for constructing a minimum-weight k-edge connected Steiner network which has approximation ratio of for even k and for odd k.