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)]c(xz)⩽β[c(xy)+c(yz)] for all x,y,z∈Vx,y,z∈V, which varies from uniform costs (β=1/2β=1/2) to metric costs (β=1β=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⩾4k⩾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 Subsetk-CS and Rooted SND, our ratios are 2β31−3β2 for directed graphs and β1−β for subsetk-CS on undirected graphs.