Approximation Algorithms for Network Design with Metric Costs
Joseph Cheriyan, Adrian R. Vetta · SIAM Journal on Discrete Mathematics · 2007
We study undirected networks with edge costs that satisfy the triangle inequality. Let n denote the number of nodes. We present an $O(1)$-approximation algorithm for a generalization of the metric-cost subset k-node-connectivity problem. Our approximation guarantee is proved via lower bounds that apply to the simple edge-connectivity version of the problem, where the requirements are for edge-disjoint paths rather than for openly node-disjoint paths. A corollary is that, for metric costs and for each $k=1,2,\dots,n-1$, there exists a k-node connected graph whose cost is within a factor of ${ 22\/}$ of the cost of any simple k-edge connected graph. Based on our $O(1)$-approximation algorithm, we present an $O(\log r_{\max})$-approximation algorithm for the metric-cost node-connectivity survivable network design problem, where $r_{\max}$ denotes the maximum requirement over all pairs of nodes. Our results contrast with the case of edge costs of 0 or 1, where Kortsarz, Krauthgamer, and Lee. [SIAM J. Comput., 33 (2004), pp. 704–720] recently proved, assuming NP$ subseteq\;$DTIME($n^{polylog(n)}$), a hardness-of-approximation lower bound of $2^{\log^{1-\epsilon}n}$ for the subset k-node-connectivity problem, where $\epsilon$ denotes a small positive number.