Approximation Algorithms for (S,T)-Connectivity Problems

algorithm;approximation algorithm;connectivity;directed graph;Combinatorics and Optimization

Laekhanukit, Bundit

University of Waterloo

关键词: algorithm;    approximation algorithm;    connectivity;    directed graph;    Combinatorics and Optimization;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/5321/1/stconn-thesis.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

We study a directed network design problem called the $k$-$(S,T)$-connectivity problem; we design and analyze approximationalgorithms 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 deferprecise 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 klog n)$-approximation algorithm,where $n$ denotes the number of vertices. The approximation guaranteealmost matches the best approximation guarantee known for the minimumcost $k$-vertex connected spanning subgraph problem which is $O(logklogfrac{n}{n-k})$ due to Nutov in 2009.