Approximation algorithms for connectivity augmentation problems
share
In Connectivity Augmentation problems we are given a graph H=(V,E_H) and an edge set E on V, and seek a min-size edge set J ⊆ E such that H ∪ J has larger edge/node connectivity than H. In the Edge-Connectivity Augmentation problem we need to increase the edge-connectivity by 1. In the Block-Tree Augmentation problem H is connected and H ∪ S should be 2-connected. In Leaf-to-Leaf Connectivity Augmentation problems every edge in E connects minimal deficient sets. For this version we give a simple combinatorial approximation algorithm with ratio 5/3, improving the previous 1.91 approximation that applies for the general case. We also show by a simple proof that if the Steiner Tree problem admits approximation ratio α then the general version admits approximation ratio 1+ln(4-x)+ϵ, where x is the solution to the equation 1+ln(4-x)=α+(α-1)x. For the currently best value of α=ln 4+ϵ this gives ratio 1.942. This is slightly worse than the best ratio 1.91, but has the advantage of using Steiner Tree approximation as a "black box", giving ratio < 1.9 if ratio α≤ 1.35 can be achieved.
READ FULL TEXT