An almost O(log k)-approximation for k-connected subgraphs

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

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(p·log k)-approximation for k-Connected Subgraph. Fakcharoenphol and Laekhanukit showed that k-Connectivity Augmentation admits an O(log ν)-approximation algorithm, where ν is the number of minimal "violated" sets in J. However, we may have ν = Θ(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 ν ≤ 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 = max t∈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(k 8 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 log 2 n) for node-costs.

שפה מקוריתאנגלית
כותר פרסום המארחProceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms
מוציא לאורAssociation for Computing Machinery
עמודים912-921
מספר עמודים10
מסת"ב (מודפס)9780898716801
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2009
אירוע20th Annual ACM-SIAM Symposium on Discrete Algorithms - New York, NY, ארצות הברית
משך הזמן: 4 ינו׳ 20096 ינו׳ 2009

סדרות פרסומים

שםProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

כנס

כנס20th Annual ACM-SIAM Symposium on Discrete Algorithms
מדינה/אזורארצות הברית
עירNew York, NY
תקופה4/01/096/01/09

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'An almost O(log k)-approximation for k-connected subgraphs'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי