Improved Approximation Algorthmsor Uniform Connectivity Problems

Improved Approximation Algorthmsor Uniform Connectivity Problems

##### Files

##### Publication or External Link

##### Date

1998-10-15

##### Authors

Khuller, Samir

Raghavachari, Balaji

##### Advisor

##### Citation

##### DRUM DOI

##### Abstract

The problem of finding minimum weight spanning subgraphs with a given
connectivity requirement is considered. The problem is NP-hard when the
connectivity requirement is greater than one. Polynomial time
approximation algorithms for various weighted and unweighted connectivity
problems are given.
The following results are presented:
1. For the unweighted k-edge-connectivity problem an approximation
algorithm that achieves a performance ratio of 1.85 is described. This is
the first polynomial-time algorithm that achieves a constant less than 2,
for all k.
2. For the weighted vertex-connectivity problem, a constant factor
approximation algorithm is given assuming that the edge-weights satisfy
the triangle inequality. This is the first constant factor approximation
algorithm for this problem.
3. For the case of biconnectivity, with no assumptions about the weights
of the edges, an algorithm that achieves a factor asymptotically
approaching 2 is described. This matches the previous best bound for the
corresponding edge connectivity problem.
(Also cross-referenced as UMIACS-TR-95-21)