|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 ABSTRACT
We consider two cases of the Survivable Network Design (SND) problem: given a complete graph Gn = (V, En) with costs on the edges and connectivity requirements {r(u, v): u, v ∈ V}, find a minimum cost subgraph G of Gn that contains r(u, v) internally disjoint uv-paths for all u, v ∈ V. Our main result is an O (log k · log n/n--k)-approximation algorithm for the k-Connected Subgraph problem (the case r(u, v) = k for all u, v ∈ V.), for both directed and undirected graphs, where n = |V|. Our ratio is O(log k), unless k = n - o(n). Previously, the best known approximation guarantees for this problem were O(log2 k) for directed/undirected graphs [Kortsarz and Nutov STOC 2004, Fakcharoenphol and Laekhanukit STOC 2008], and O(log k) for undirected graphs with k ≤ √n/2 [Cheriyan, Vempala, and Vetta STOC 2002]. As in previous work, we consider the k-Connectivity Augmentation problem of increasing at minimum cost the connectivity of a given graph J from k - 1 to k; a ρ-approximation for it is used to derive an O(ρ · log k)-approximation for k-Connected Subgraph. Fakcharoenphol and Laekhanukit showed that k-Connectivity Augmentation admits an O(log v)-approximation algorithm, where v is the number of minimal "violated" sets in J. However, we may have v = θ(n), so this gives only an O(log n)-approximation. We design a novel primal-dual algorithm that adds an edge set of cost ≤ opt to get v ≤ 2n/n - k. Combined with the algorithm of Fakcharoenphol and Laekhanukit, this gives the ratio O (log n/n - k) for k-Connectivity Augmentation, which is O(1), unless k = n - o(n). Our additional result is for the (undirected) Rooted SND, where for a "root" s ∈ V, the connectivity requirements are {r(s, t) = r(t): t ∈ T ⊆ V}, and the solution graph should contain r(t) internally disjoint st-paths for all t ∈ T. For large values of k = maxt∈T r(t) Rooted SND is at least as hard to approximate as Directed Steiner Tree [Lando and Nutov APPROX 2008]. For Rooted SND [Chakraborty, Chuzhoy, Khanna STOC 08] gave recently a kO(k2) log4 n-approximation algorithm. Slightly later [Chuzhoy and Khanna FOCS 08] improved the ratio to O(k2 log n), and also gave an O(k8 log2 n)-approximation algorithm for the case of node-costs. Independently, we obtained a simple approximation algorithm with ratios O(k2 log n) for edge-costs, and O(k4 log2 n) for node-costs. REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
INDEX TERMS
Primary Classification:
Additional Classification:
The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage Privacy Policy Code of Ethics Contact Us Useful downloads:  Adobe Acrobat
 QuickTime
 Windows Media Player
 Real Player
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Pdf
G.2