Approximation Algorithms for Connectivity Augmentation Problems

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


In Connectivity Augmentation problems we are given a graph H= (V, EH) and an edge set E on V, and seek a min-size edge set J⊆ E such that H∪ J has larger edge/node connectivity than H. In the Edge-Connectivity Augmentation problem we need to increase the edge-connectivity by 1. In the Block-Tree Augmentation problem H is connected and H∪ S should be 2-connected. In Leaf-to-Leaf Connectivity Augmentation problems every edge in E connects minimal deficient sets. For this version we give a simple combinatorial approximation algorithm with ratio 5/3, improving the 1.91 approximation of [6] (see also [23]), that applies for the general case. We also show by a simple proof that if the Steiner Tree problem admits approximation ratio α then the general version admits approximation ratio 1 + ln (4 - x) + ϵ, where x is the solution to the equation 1 + ln (4 - x) = α+ (α- 1 ) x. For the currently best value of α= ln 4 + ϵ [7] this gives ratio 1.942. This is slightly worse than the ratio 1.91 of [6], but has the advantage of using Steiner Tree approximation as a “black box”. In the Element Connectivity Augmentation problem we are given a graph G= (V, E), S⊆ V, and connectivity requirements r= { r(u, v): u, v∈ S}. The goal is to find a min-size set J of new edges on S such that for all u, v∈ S the graph G∪ J contains r(u, v) uv-paths such that no two of them have an edge or a node in V\ S in common. The problem is NP-hard even when rmax=maxu,v∈Sr(u,v)=2. We obtain ratio 3/2, improving the previous ratio 7/4 of [22]. For the case of degree bounds on S we obtain the same ratio with just + 1 degree violation, which is tight, since deciding whether there exists a feasible solution is NP-hard even when rmax= 2.

שפה מקוריתאנגלית
כותר פרסום המארחComputer Science – Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Proceedings
עורכיםRahul Santhanam, Daniil Musatov
מוציא לאורSpringer Science and Business Media Deutschland GmbH
מספר עמודים18
מסת"ב (מודפס)9783030794156
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2021
אירוע16th International Computer Science Symposium in Russia, CSR 2021 - Sochi, רוסיה
משך הזמן: 28 יוני 20212 יולי 2021

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

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך12730 LNCS
ISSN (מודפס)0302-9743
ISSN (אלקטרוני)1611-3349


כנס16th International Computer Science Symposium in Russia, CSR 2021

הערה ביבליוגרפית

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Approximation Algorithms for Connectivity Augmentation Problems'. יחד הם יוצרים טביעת אצבע ייחודית.

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