Inapproximability of survivable networks

Yuval Lando; Zeev Nutov

doi:10.1007/978-3-540-85363-3_12

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
المعرِّفات الرقمية للأشياء	https://doi.org/10.1007/978-3-540-85363-3_12
حالة النشر	نُشِر - 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, الولايات المتّحدة المدة: 25 أغسطس 2008 → 27 أغسطس 2008

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

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

!!Conference

!!Conference	11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and 12th International Workshop on Randomization and Computation, RANDOM 2008
الدولة/الإقليم	الولايات المتّحدة
المدينة	Boston, MA
المدة	25/08/08 → 27/08/08

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

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: [email protected] (Y. Lando), [email protected] (Z. Nutov).

الوصول إلى المستند

10.1007/978-3-540-85363-3_12

الملفات والروابط الأخرى

Link to publication in Scopus

قم بذكر هذا

Lando, Y., & Nutov, Z. (2008). Inapproximability of survivable networks. في Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings (الصفحات 146-152). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); المجلد 5171 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-85363-3_12

Lando, Yuval ; Nutov, Zeev. / Inapproximability of survivable networks. Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings. Springer Verlag, 2008. الصفحات 146-152 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{145e31fd61344bf88b1b9ce9b5a62b9d,

title = "Inapproximability of survivable networks",

abstract = "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.",

author = "Yuval Lando and Zeev Nutov",

note = "Funding Information: This research was supported by The Open University of Israel{\textquoteright}s Research Fund (grant no. 100685). Preliminary version in APPROX, LNCS 5171, pages 146{\textendash}152. Tel.: +972 9 778 1254; fax: +972 9 778 2605. E-mail addresses: [email protected] (Y. Lando), [email protected] (Z. Nutov).; 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and 12th International Workshop on Randomization and Computation, RANDOM 2008 ; Conference date: 25-08-2008 Through 27-08-2008",

year = "2008",

doi = "10.1007/978-3-540-85363-3\_12",

language = "אנגלית",

isbn = "3540853626",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "146--152",

booktitle = "Approximation, Randomization and Combinatorial Optimization",

address = "גרמניה",

}

Lando, Y & Nutov, Z 2008, Inapproximability of survivable networks. في Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), المجلد 5171 LNCS, Springer Verlag, الصفحات 146-152, 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and 12th International Workshop on Randomization and Computation, RANDOM 2008, Boston, MA, الولايات المتّحدة, 25/08/08. https://doi.org/10.1007/978-3-540-85363-3_12

Inapproximability of survivable networks. / Lando, Yuval; Nutov, Zeev.
Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings. Springer Verlag, 2008. صفحة 146-152 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); المجلد 5171 LNCS).

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

TY - GEN

T1 - Inapproximability of survivable networks

AU - Lando, Yuval

AU - Nutov, Zeev

N1 - 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: [email protected] (Y. Lando), [email protected] (Z. Nutov).

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/51849150833

U2 - 10.1007/978-3-540-85363-3_12

DO - 10.1007/978-3-540-85363-3_12

M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???

AN - SCOPUS:51849150833

SN - 3540853626

SN - 9783540853626

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 146

EP - 152

BT - Approximation, Randomization and Combinatorial Optimization

PB - Springer Verlag

T2 - 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and 12th International Workshop on Randomization and Computation, RANDOM 2008

Y2 - 25 August 2008 through 27 August 2008

ER -

Lando Y, Nutov Z. Inapproximability of survivable networks. في Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings. Springer Verlag. 2008. صفحة 146-152. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-85363-3_12

Inapproximability of survivable networks

ملخص

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

!!Conference

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

الوصول إلى المستند

الملفات والروابط الأخرى

بصمة

قم بذكر هذا