Approximating survivable networks with β-metric costs

The Survivable Network Design (SND) problem seeks a minimum-cost subgraph that satisfies prescribed node-connectivity requirements. We consider SND on both directed and undirected complete graphs with β-metric costs when c(xz)≤β[c(xy)+c(yz)] for all x,y,z ∈ V, which varies from uniform costs (β=1/2) to metric costs (β=1). For the k-Connected Subgraph (k-CS) problem our ratios are: 1+2βk(1-β)-12k-1 for undirected graphs, and 1+4β3k(1-3β2)-12k-1 for directed graphs and 12≤β<13. For undirected graphs this improves the ratios β1-β of Böckenhauer et al. (2008) [3] and 2+βkn of Kortsarz and Nutov (2003) [11] for all k≥4 and 12+3k-22(4k2-7k+2)≤β≤k2(k+1)2-2. We also show that SND admits the ratios 2β1-β for undirected graphs, and 4β31-3β2 for directed graphs with 1/2≤β<1/3. For two important particular cases of SND, so-called Subset k-CS and Rooted SND, our ratios are 2β31-3β2 for directed graphs and β1-β for subset k-CS on undirected graphs.