Computer Science – Data Structures and Algorithms
Scientific paper
2011-04-20
Computer Science
Data Structures and Algorithms
Scientific paper
The minimum-cost subset $k$-connected subgraph problem is a cornerstone problem in the area of network design with vertex connectivity requirements. In this problem, we are given a graph $G=(V,E)$ with costs on edges and a set of terminals $T$. The goal is to find a minimum cost subgraph such that every pair of terminals are connected by $k$ openly (vertex) disjoint paths. In this paper, we present an approximation algorithm for the subset $k$-connected subgraph problem which improves on the previous best approximation guarantee of $O(k^2\log{k})$ by Nutov (FOCS 2009). Our approximation guarantee, $\alpha(|T|)$, depends upon the number of terminals: [\alpha(|T|) \ \ =\ \ O(|T|^2) & if |T| < 2k O(k \log^2 k) & if 2k\le |T| < k^2 O(k \log k) & if |T| \ge k^2] So, when the number of terminals is {\em large enough}, the approximation guarantee improves significantly. Moreover, we show that, given an approximation algorithm for $|T|=k$, we can obtain almost the same approximation guarantee for any instances with $|T|> k$. This suggests that the hardest instances of the problem are when $|T|\approx k$.
No associations
LandOfFree
An improved approximation algorithm for the minimum-cost subset k-connected subgraph problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An improved approximation algorithm for the minimum-cost subset k-connected subgraph problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An improved approximation algorithm for the minimum-cost subset k-connected subgraph problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-431974