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)
סטטוס פרסוםפורסם - 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 אוג׳ 200827 אוג׳ 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/0827/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: ylando@hotmail.com (Y. Lando), nutov@openu.ac.il (Z. Nutov).

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Inapproximability of survivable networks'. יחד הם יוצרים טביעת אצבע ייחודית.

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