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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2021
الحدث16th International Computer Science Symposium in Russia, CSR 2021 - Sochi, روسيا
المدة: ٢٨ يونيو ٢٠٢١٢ يوليو ٢٠٢١

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت12730 LNCS
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349


!!Conference16th International Computer Science Symposium in Russia, CSR 2021

ملاحظة ببليوغرافية

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.


أدرس بدقة موضوعات البحث “Approximation Algorithms for Connectivity Augmentation Problems'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا