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

Abstract

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$ of additional points such that the unit-disc graph of $R\cup S$ contains $r_{uv}$ pairwise internally edge-disjoint and $(B\cup S)$-disjoint $uv$-paths for all $u,v\in R$. The case when $r_{uv}=1$ for all $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 $\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 $\Delta =5$ in ${\mathbb{R}}^2$ The previous known approximation ratio for {\sf ST-MSP} was $\lfloor (\Delta +1)/2\rfloor +1+\epsilon$ in an arbitrary normed space \cite{NY}, and $2.5+\epsilon$ in the Euclidean space ${\mathbb{R}}^2$ \cite{cheng2008relay}. Our approximation ratio for ST-MSP is $1+\ln (\Delta -1)+\epsilon$ in an arbitrary normed space, which in ${\mathbb{R}}^2$ reduces to $1+\ln 4+\epsilon <2.3863+\epsilon$. For SN-MSP with $r_{uv}\in \{0,1,2\}$, we give a simple $\Delta$-approximation algorithm. In particular, for SF-MSP, this improves the previous ratio $2\Delta$.