2-Node-Connectivity Network Design

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

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 ספט׳ 202010 ספט׳ 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/2010/09/20

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

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום '2-Node-Connectivity Network Design'. יחד הם יוצרים טביעת אצבע ייחודית.

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