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
عدد الصفحات16
رقم المعيار الدولي للكتب (المطبوع)9783030808785
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2021
الحدث18th International Workshop on Approximation and Online Algorithms, WAOA 2019 - Virtual, Online
المدة: ٩ سبتمبر ٢٠٢٠١٠ سبتمبر ٢٠٢٠

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

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


!!Conference18th International Workshop on Approximation and Online Algorithms, WAOA 2019
المدينةVirtual, Online

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

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.


أدرس بدقة موضوعات البحث “2-Node-Connectivity Network Design'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا