On shortest \(k\)-edge-connected Steiner networks in metric spaces (Q1977864): Difference between revisions

A \(k\)-edge-connected Steiner network on \(P\) is a multigraph containing the finite set \(P\) of points as nodes and allowing \(k\)-edge disjoint paths between any pair of points in \(P\). The generalizes Steiner ratio \(r_k\) gives the best (taken over all \(P)\) lower bound for the ratio between the length of a shortest \(k\)-edge-connected Steiner network and the shortest \(k\)-edge-connected spanning network on \(P\). The authors show that in any metric space \(r_k\geq 3/4\) for \(k\geq 2\) and prove the existence of a polynomial time \(\alpha\)-approximation for the shortest \(k\)-edge-connected Steiner network with \(\alpha= 2\) for even \(k\) and \(\alpha= 2+4/3k\) for odd \(k\). In the special case of the Euclidean plane they prove that \(r_k\geq\sqrt {3\over 2}\), \(r_3\leq(\sqrt 3+2)/4\) and \(r_4\leq(7+3 \sqrt 3)(0+2\sqrt 3)\).