Improved approximation algorithms for some capacitated k edge connectivity problems
share
We consider the following two variants of the Capacitated k-Edge Connected Subgraph (Cap-k-ECS) problem. Near Min-Cuts Cover: Given a graph G=(V,E) with edge costs and E_0 ⊆ E, find a min-cost edge set J ⊆ E ∖ E_0 that covers all cuts with at most k-1 edges of the graph G_0=(V,E_0). We obtain approximation ratio k-λ_0+1+ϵ, improving the ratio 2min{k-λ_0,8} of Bansal, Cheriyan, Grout, and Ibrahimpur for k-λ_0 ≤ 14,where λ_0 is the edge connectivity of G_0. (k,q)-Flexible Graph Connectivity ((k,q)-FGC): Given a graph G=(V,E) with edge costs and a set U ⊆ E of ”unsafe” edges and integers k,q, find a min-cost subgraph H of G such that every cut of H has at least k safe edges or at least k+q edges. We show that (k,1)-FGC admits approximation ratio 3.5+ϵ if k is odd (improving the previous ratio 4), and that (k,2)-FGC admits approximation ratio 6 if k is even and 7+ϵ if k is odd (improving the previous ratio 20).
READ FULL TEXT