תקציר
We consider network design problems in which we are given a graph G= (V, E) with edge costs, and seek a min-cost/size 2-node-connected subgraph G′= (V′, E′) that satisfies a prescribed property. In the Block-Tree Augmentation problem the goal is to augment a tree T by a min-size edge set F⊆ E such that G′= T∪ F is 2-node-connected. We break the natural ratio of 2 for this problem and show that it admits approximation ratio 1.91. This result extends to the related Crossing Family Augmentation problem.In the 2-Connected Dominating Set problem G′ should dominate V. We give the first non-trivial approximation algorithm for this problem, with expected ratio O~ (log4| V| ).In the 2-Connected Quota Subgraph problem we are given node profits p(v) and G′ should have profit at least a given quota Q. We show expected ratio O~ (log2| V| ), almost matching the best known ratio O(log2| V| ). Our algorithms are very simple, and they combine three main ingredients: 1.A probabilistic spanning tree embedding with distortion O~ (log | V| ) results in a variant of the Block-Tree Augmentation problem.2.An approximation ratio preserving reduction of Block-Tree Augmentation variants to Node Weighted Steiner Tree problems.3.Using existing approximation algorithms for variants of the Node Weighted Steiner Tree problem.
שפה מקורית | אנגלית |
---|---|
כותר פרסום המארח | Approximation and Online Algorithms - 18th International Workshop, WAOA 2020, Revised Selected Papers |
עורכים | Christos Kaklamanis, Asaf Levin |
מוציא לאור | Springer Science and Business Media Deutschland GmbH |
עמודים | 220-235 |
מספר עמודים | 16 |
מסת"ב (מודפס) | 9783030808785 |
מזהי עצם דיגיטלי (DOIs) | |
סטטוס פרסום | פורסם - 2021 |
אירוע | 18th International Workshop on Approximation and Online Algorithms, WAOA 2019 - Virtual, Online משך הזמן: 9 ספט׳ 2020 → 10 ספט׳ 2020 |
סדרות פרסומים
שם | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
כרך | 12806 LNCS |
ISSN (מודפס) | 0302-9743 |
ISSN (אלקטרוני) | 1611-3349 |
כנס
כנס | 18th International Workshop on Approximation and Online Algorithms, WAOA 2019 |
---|---|
עיר | Virtual, Online |
תקופה | 9/09/20 → 10/09/20 |
הערה ביבליוגרפית
Publisher Copyright:© 2021, Springer Nature Switzerland AG.