We study a directed network design problem called the $k$-$(S,T)$-connectivity problem; we design and analyze approximation
algorithms and give hardness results. For each positive integer $k$, the minimum cost $k$-vertex connected spanning subgraph problem is a special case of the $k$-$(S,T)$-connectivity problem. We defer
precise statements of the problem and of our results to the introduction.
For $k=1$, we call the problem the $(S,T)$-connectivity problem. We study three variants of the problem: the standard
$(S,T)$-connectivity problem, the relaxed $(S,T)$-connectivity problem, and the unrestricted $(S,T)$-connectivity problem. We give hardness results for these three variants. We design a $2$-approximation algorithm for the standard $(S,T)$-connectivity problem. We design tight approximation algorithms for the relaxed $(S,T)$-connectivity problem and one of its special cases.
For any $k$, we give an $O(\log k\log n)$-approximation algorithm,
where $n$ denotes the number of vertices. The approximation guarantee
almost matches the best approximation guarantee known for the minimum
cost $k$-vertex connected spanning subgraph problem which is $O(\log
k\log\frac{n}{n-k})$ due to Nutov in 2009.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/5321 |
| Date | 27 July 2010 |
| Creators | Laekhanukit, Bundit |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.0018 seconds