Approximating minimum cost connectivity problems

Abstract

We survey approximation algorithms of connectivity problems.
The survey presented describing various  techniques. In the talk the following techniques and results are presented. 

1)Outconnectivity:   Its well known that there exists a polynomial time algorithm to solve the problems of finding an edge k-outconnected from r subgraph  [EDMONDS]  and a vertex k-outconnectivity subgraph from r [Frank-Tardos] . 
We show how to use this to obtain a ratio 2 approximation for the min cost edge k-connectivity 
problem. 

2)The critical cycle theorem of Mader: We state  a fundamental theorem of Mader and use it to provide a 1+(k-1)/n ratio approximation for the min cost vertex k-connected subgraph, in the metric case.
We also show results for the min power vertex k-connected problem using this lemma.
We show that the min power is equivalent to the min-cost case with respect to approximation.

3)Laminarity and uncrossing:  We use the well known laminarity of a  BFS solution and show a simple new proof  due to Ravi et al for Jain's  2 approximation  for Steiner network.