Inapproximability of survivable networks

Yuval Lando, Zeev Nutov

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

In the Survivable Network Design Problem (SNDP) one seeks to find a minimum cost subgraph that satisfies prescribed node-connectivity requirements. We give a novel approximation ratio preserving reduction from Directed SNDP to Undirected SNDP. Our reduction extends and widely generalizes as well as significantly simplifies the main results of [6]. Using it, we derive some new hardness of approximation results, as follows. We show that directed and undirected variants of SNDP and of k -Connected Subgraph are equivalent w.r.t. approximation, and that a ρ-approximation for Undirected Rooted SNDP implies a ρ-approximation for Directed Steiner Tree.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفApproximation, Randomization and Combinatorial Optimization
العنوان الفرعي لمنشور المضيفAlgorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings
ناشرSpringer Verlag
الصفحات146-152
عدد الصفحات7
رقم المعيار الدولي للكتب (المطبوع)3540853626, 9783540853626
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2008
الحدث11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and 12th International Workshop on Randomization and Computation, RANDOM 2008 - Boston, MA, الولايات المتّحدة
المدة: ٢٥ أغسطس ٢٠٠٨٢٧ أغسطس ٢٠٠٨

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

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

!!Conference

!!Conference11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and 12th International Workshop on Randomization and Computation, RANDOM 2008
الدولة/الإقليمالولايات المتّحدة
المدينةBoston, MA
المدة٢٥/٠٨/٠٨٢٧/٠٨/٠٨

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

Funding Information:
This research was supported by The Open University of Israel’s Research Fund (grant no. 100685). Preliminary version in APPROX, LNCS 5171, pages 146–152. Tel.: +972 9 778 1254; fax: +972 9 778 2605. E-mail addresses: ylando@hotmail.com (Y. Lando), nutov@openu.ac.il (Z. Nutov).

بصمة

أدرس بدقة موضوعات البحث “Inapproximability of survivable networks'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا