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~(1/2)/2, r_3 ≤ (3~(1/2) + 2)/4 and r_4 ≤ (7 + 3(3~(1/2)))/(9 + 2(3~(1/2))).