A (4+ε)-approximation for k-connected subgraphs

01/22/2019
by   Zeev Nutov, et al.
0

We obtain approximation ratio 2(2+1/ℓ) for the (undirected) k-Connected Subgraph problem, where ℓ≈1/2 (_k n-1) is the largest integer such that 2^ℓ-1 k^2ℓ+1≤ n. For large values of n this improves the 6-approximation of Cheriyan and Végh when n =Ω(k^3), which is the case ℓ=1. For k bounded by a constant we obtain ratio 4+ϵ. For large values of n our ratio matches the best known ratio 4 for the augmentation version of the problem, as well as the best known ratios for k=6,7. Similar results are shown for the problem of covering an arbitrary crossing supermodular biset function.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset