An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity Problem

In the survivable network design problem (SNDP), given an undirected graph and values r/sub ij/ for each pair of vertices i and j, we attempt to find a minimum-cost subgraph such that there are r/sub ij/ disjoint paths between vertices i and j. In the edge connected version of this problem (EC-SNDP), these paths must be edge-disjoint. In the vertex connected version of the problem (VC-SNDP), the paths must be vertex disjoint. K. Jain et al. (1999) propose a version of the problem intermediate in difficulty to these two, called the element connectivity problem (ELC-SNDP, or ELC). These variants of SNDP are all known to be NP-hard. The best known approximation algorithm for the EC-SNDP has performance guarantee of 2 (K. Jain, 2001), and iteratively rounds solutions to a linear programming relaxation of the problem. ELC has a primal-dual O (log k) approximation algorithm, where k=max/sub i, j/ r/sub ij/. VC-SNDP is not known to have a non-trivial approximation algorithm; however, recently L. Fleischer (2001) has shown how to extend the technique of K. Jain ( 2001) to give a 2-approximation algorithm in the case that r/sub ij//spl isin/{0, 1, 2}. She also shows that the same techniques will not work for VC-SNDP for more general values of r/sub ij/. The authors show that these techniques can be extended to a 2-approximation algorithm for ELC. This gives the first constant approximation algorithm for a general survivable network design problem which allows node failures.

Authors

• Lisa Fleischer
• Kamal Jain
• David P. Williamson

Keywords

• Iterative algorithms
• Approximation algorithms
• Algorithm design and analysis
• Linear programming
• Robustness
• Computer science
• Polynomials
• Algorithm For Problem
• Connectivity Problems
• 2-approximation Algorithm
• Undirected
• Estimation Algorithm
• Network Path
• Non-terminal
• Edge Connectivity
• Performance Guarantees
• Node Failure
• Linear Relaxation
• Linear Programming Relaxation
• Terminal Pair
• Basic Solution
• Collection Of Sets
• Forest Structure
• Pair Of Sets
• Polynomial-time Algorithm
• Partial Order
• Complementary Pairing