## תקציר

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 |

עמודים | 190-204 |

מספר עמודים | 15 |

מסת"ב (מודפס) | 9783031498145 |

מזהי עצם דיגיטלי (DOIs) | |

סטטוס פרסום | פורסם - 2023 |

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

מדינה/אזור | הולנד |

עיר | Amsterdam |

תקופה | 7/09/23 → 8/09/23 |

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

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