Improved Approximations for Relative Survivable Network Design

Michael Dinitz, Ama Koranteng, Guy Kortsarz, Zeev Nutov

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء


One of the most important and well-studied settings for network design is edge-connectivity requirements. This encompasses uniform demands (e.g. the Minimum k-Edge-Connected Spanning Subgraph problem), as well as nonuniform demands (e.g. the Survivable Network Design problem (SND)). In a recent paper [Dinitz, Koranteng, Kortsarz APPROX ’22], the authors observed that a weakness of these formulations is that we cannot consider fault-tolerance in graphs that have small cuts but where some large fault sets can still be accommodated. To remedy this, they introduced new variants of these problems under the notion relative fault-tolerance. Informally, this requires not that two nodes are connected if there are a bounded number of faults (as in the classical setting), but that they are connected if there are a bounded number of faults and the nodes are connected in the underlying graph post-faults. Due to difficulties introduced by this new notion of fault-tolerance, the results in [Dinitz, Koranteng, Kortsarz APPROX ’22] are quite limited. For the Relative Survivable Network Design problem (RSND) with non-uniform demands, they are only able to give a nontrivial result when there is a single demand with connectivity requirement 3—a non-optimal 27/4-approximation. We strengthen this result in two significant ways: We give a 2-approximation for RSND when all requirements are at most 3, and a -approximation for RSND with a single demand of arbitrary value k. To achieve these results, we first use the “cactus representation” of minimum cuts to give a lossless reduction to normal SND. Second, we extend the techniques of [Dinitz, Koranteng, Kortsarz APPROX’22] to prove a generalized and more complex version of their structure theorem, which we then use to design a recursive approximation algorithm.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفApproximation and Online Algorithms - 21st International Workshop, WAOA 2023, Proceedings
المحررونJarosław Byrka, Andreas Wiese
ناشرSpringer Science and Business Media Deutschland GmbH
عدد الصفحات15
رقم المعيار الدولي للكتب (المطبوع)9783031498145
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2023
الحدث21st International Workshop on Approximation and Online Algorithms, WAOA 2023 - Amsterdam, هولندا
المدة: ٧ سبتمبر ٢٠٢٣٨ سبتمبر ٢٠٢٣

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

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


!!Conference21st International Workshop on Approximation and Online Algorithms, WAOA 2023

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

Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.


أدرس بدقة موضوعات البحث “Improved Approximations for Relative Survivable Network Design'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا