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
מזהי עצם דיגיטלי (DOIs)	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
ISSN (מודפס)	0302-9743
ISSN (אלקטרוני)	1611-3349

כנס

כנס	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–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

תקציר

סדרות פרסומים

כנס

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

גישה למסמך

קבצים וקישורים אחרים

טביעת אצבע

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