Paper Info
Title
Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
Abstract
The survivable network design problem (SNDP) is the following problem: given an undirected graph and values rij for each pair of vertices i and j, find a minimum-cost subgraph such that there are at least rij 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. The element connectivity problem (ELC-SNDP, or ELC) is a problem of intermediate difficulty. In this problem, the set of vertices is partitioned into terminals and nonterminals. The edges and nonterminals of the graph are called elements. The values rij are only specified for pairs of terminals i, j, and the paths from i to j must be element disjoint. Thus if rij-1 elements fail, terminals i and j are still connected by a path in the network.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 and iteratively rounds solutions to a linear programming relaxation of the problem. ELC has a primal-dual O(log k)-approximation algorithm, where k = maxi,j rij. Since this work first appeared as an extended abstract, it has been shown that it is hard to approximate VC-SNDP to factor 2log1-εn.In this paper we investigate applying iterative rounding to ELC and VC-SNDP We show that iterative rounding will not yield a constant factor approximation algorithm for general VC-SNDP. On the other hand, we show how to extend the analysis of iterative rounding applied to EC-SNDP to yield 2-approximation algorithms for both general ELC, and for the case of VC-SNDP when rij ∈ {0, 1, 2}. The latter result improves on an existing 3-approximation algorithm. The former is the first constant factor approximation algorithm for a general survivable network design problem that allows node failures.
Year
DOI
Venue
2006
10.1016/j.jcss.2005.05.006
J. Comput. Syst. Sci.
Keywords
Field
DocType
vertices i,approximate vc-sndp,following problem,constant factor approximation algorithm,general vc-sndp,approximation algorithm,network design,element connectivity problem,3-approximation algorithm,iterative rounding 2-approximation algorithm,minimum-cost vertex connectivity problem,2-approximation algorithm,survivable network design problem
Discrete mathematics,Approximation algorithm,Graph,Combinatorics,Disjoint sets,Network planning and design,Vertex (geometry),Rounding,Vertex connectivity,Linear programming relaxation,Mathematics
Journal
Volume
Issue
ISSN
72
5
Journal of Computer and System Sciences
Citations 
PageRank 
References 
48
1.60
15
Authors
3
Name
Order
Citations
PageRank
Lisa Fleischer1562.09
Kamal Jain23563295.66
David P. Williamson33564413.34