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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2023
אירוע21st International Workshop on Approximation and Online Algorithms, WAOA 2023 - Amsterdam, הולנד
משך הזמן: 7 ספט׳ 20238 ספט׳ 2023

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

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


כנס21st 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'. יחד הם יוצרים טביעת אצבע ייחודית.

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