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)