APPROXIMATION ALGORITHMS FOR NETWORK DESIGN WITH METRIC COSTS

摘要

We study undirected networks wih 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,..., 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 is not an element of DTIME(n~(polylog(n)), a hardness-of-approximation lower bound of 2~(log~(1-ε)n) for the subset k-node-connectivity problem, where ε denotes a small positive number.