Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
A 2-Approximation for Minimum Cost {0, 1, 2} Vertex Connectivity
| |
|
A 2-Approximation for Minimum Cost {0, 1, 2} Vertex Connectivity
Lisa Fleischer6 
| (6) |
Graduate School of Industrial Administration, Carnegie Mellon University, 5000 Forbes Ave, Pittsburgh, PA 15217, USA |
Abstract
In survivable network design, each pair ( i, j) of vertices is assigned a level of importance r
ij. The vertex connectivity problem is to design a minimum cost network such that between each pair of vertices with importance
level r, there are r vertex disjoint paths. There is no approximation algorithm known for this general problem. In this paper, we give a 2-approximation
for the problem when r ∈ {0, 1, 2} V xV, improving on a previous known 3-approximation. This matches the best known approximation for the easier problem that requires
that the paths be only edge-disjoint.
Our algorithm extends an iterative rounding algorithm that gives a 2-approximation for the edge-connectivity problem, for
arbitrary connectivity requirements r. (K. Jain, A factor 2 approximation for the gen- eralized Steiner network problem.) This algorithm relies on well-known uncrossing
lemma for tight edge cutsets. Our extension uses a new type of uncrossing lemma for tight cutsets that may include vertices
as well as edges.
For r ∈ {1, k}V xV, k ≥ 3, we show that a) uncrossing tight cutsets is not possible, and b) any analysis for iterative rounding that depends directly
on the largest fractional value in the linear programming solution cannot provide approximation guarantees better than the
maximum connectivity requirement.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|