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$ 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 $Δ$ 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 $Δ=5$ in $\mathbb{R}^2$ The previous known approximation ratio for {\sf ST-MSP} was $\lfloor (Δ+1)/2 \rfloor+1+ε$ in an arbitrary normed space \cite{NY}, and $2.5+ε$ in the Euclidean space $\mathbb{R}^2$ \cite{cheng2008relay}. Our approximation ratio for ST-MSP is $1+\ln(Δ-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 $Δ$-approximation algorithm. In particular, for SF-MSP, this improves the previous ratio $2Δ$.

No reviews yet.

No comments yet.