Approximating {0,1,2}-Survivable Networks with Minimum Number of Steiner Points

We consider low connectivity variants of the Survivable Network with Minimum Number of Steiner Points (SN-MSP) problem: given a finite set $R$ of terminals in a metric space (M,d), a subset $B\subseteq R$ of “unstable” terminals, and connectivity requirements {r_{uv}: u,v \in R}, find a minimum size set $S \subseteq M$ofadditionalpointssuchthattheunit-discgraphof$R \cup S$contains$r_{uv}$pairwiseinternallyedge-disjointand$(B \cup S)$-disjoint$uv$-pathsforall$u,v \in R$\mathrm{.}Thecasewhen$r_{uv}=1$forall$u,v \in R$ is the {\sf Steiner Tree with Minimum Number of Steiner Points} (ST-MSP) problem, and the case $r_{uv}\in \{0,1\}$ is the {\sf Steiner Forest with Minimum Number of Steiner Points} (SF-MSP) problem. Let $\mathrm{\Delta }$ be the maximum number of points in a unit ball such that the distance between any two of them is larger than 1. It is known that $\mathrm{\Delta }=5$ in ${\mathbb{R}}^2$ The previous known approximation ratio for {\sf ST-MSP} was $\lfloor (\Delta+1)/2 \rfloor+1+\epsilon$inanarbitrarynormedspace\text{cite}NY,and$2.5+\epsilon$intheEuclideanspace$$\mathbb{R}$^2$ \cite{cheng2008relay}. Our approximation ratio for ST-MSP is $1+\ln (\mathrm{\Delta }-1)+ϵ$ in an arbitrary normed space, which in ${\mathbb{R}}^2$ reduces to $1+\ln 4+ϵ<2.3863+ϵ$. For SN-MSP with $r_{uv}\in \{0,1,2\}$, we give a simple $\mathrm{\Delta }$-approximation algorithm. In particular, for SF-MSP, this improves the previous ratio $2\mathrm{\Delta }$.