Hardness of approximation for vertex-connectivity network-design problems

Guy Kortsarz; Robert Krauthgamer; James R. Lee

doi:10.1007/3-540-45753-4_17

Hardness of approximation for vertex-connectivity network-design problems

Guy Kortsarz, Robert Krauthgamer, James R. Lee

פרסום מחקרי: פרק בספר / בדוח / בכנס › פרסום בספר כנס › ביקורת עמיתים

תקציר

In the survivable network design problem SNDP, the goal is to find a minimum-cost subgraph satisfying certain connectivity requirements. We study the vertex-connectivity variant of SNDP in which the input specifies, for each pair of vertices, a required number of vertex-disjoint paths connecting them. We give the first lower bound on the approximability of SNDP, showing that the problem admits no efficient (formula presented) ratio approximation for any fixed ε > 0 unless NP ⊆ DTIME(n^polylog(ⁿ⁾). We also show hardness of approximation results for several important special cases of SNDP, including constant factor hardness for the k-vertex connected spanning subgraph problem (k-VCSS) and for the vertex-connectivity augmentation problem, even when the edge costs are severely restricted.

שפה מקורית	אנגלית
כותר פרסום המארח	Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings
עורכים	Klaus Jansen, Stefano Leonardi, Vijay Vazirani
מוציא לאור	Springer Verlag
עמודים	185-199
מספר עמודים	15
מסת"ב (מודפס)	3540441867, 9783540441861
מזהי עצם דיגיטלי (DOIs)	https://doi.org/10.1007/3-540-45753-4_17
סטטוס פרסום	פורסם - 2002
פורסם באופן חיצוני	כן
אירוע	5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002 - Rome, איטליה משך הזמן: 17 ספט׳ 2002 → 21 ספט׳ 2002

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

שם	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך	2462
ISSN (מודפס)	0302-9743
ISSN (אלקטרוני)	1611-3349

כנס

כנס	5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002
מדינה/אזור	איטליה
עיר	Rome
תקופה	17/09/02 → 21/09/02

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

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.

גישה למסמך

10.1007/3-540-45753-4_17

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

Link to publication in Scopus

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

Kortsarz, G., Krauthgamer, R., & Lee, J. R. (2002). Hardness of approximation for vertex-connectivity network-design problems. ב- K. Jansen, S. Leonardi, & V. Vazirani (עורכים), Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings (עמודים 185-199). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); כרך 2462). Springer Verlag. https://doi.org/10.1007/3-540-45753-4_17

Kortsarz, Guy ; Krauthgamer, Robert ; Lee, James R. / Hardness of approximation for vertex-connectivity network-design problems. Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings. עורך / Klaus Jansen ; Stefano Leonardi ; Vijay Vazirani. Springer Verlag, 2002. עמודים 185-199 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{7f4c7a475ee84555b9c12e6e9ea72ea5,

title = "Hardness of approximation for vertex-connectivity network-design problems",

abstract = "In the survivable network design problem SNDP, the goal is to find a minimum-cost subgraph satisfying certain connectivity requirements. We study the vertex-connectivity variant of SNDP in which the input specifies, for each pair of vertices, a required number of vertex-disjoint paths connecting them. We give the first lower bound on the approximability of SNDP, showing that the problem admits no efficient (formula presented) ratio approximation for any fixed ε > 0 unless NP ⊆ DTIME(npolylog(n)). We also show hardness of approximation results for several important special cases of SNDP, including constant factor hardness for the k-vertex connected spanning subgraph problem (k-VCSS) and for the vertex-connectivity augmentation problem, even when the edge costs are severely restricted.",

author = "Guy Kortsarz and Robert Krauthgamer and Lee, {James R.}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2002.; 5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002 ; Conference date: 17-09-2002 Through 21-09-2002",

year = "2002",

doi = "10.1007/3-540-45753-4_17",

language = "אנגלית",

isbn = "3540441867",

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

publisher = "Springer Verlag",

pages = "185--199",

editor = "Klaus Jansen and Stefano Leonardi and Vijay Vazirani",

booktitle = "Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings",

address = "גרמניה",

}

Kortsarz, G, Krauthgamer, R & Lee, JR 2002, Hardness of approximation for vertex-connectivity network-design problems. ב- K Jansen, S Leonardi & V Vazirani (עורכים), Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), כרך 2462, Springer Verlag, עמודים 185-199, 5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002, Rome, איטליה, 17/09/02. https://doi.org/10.1007/3-540-45753-4_17

Hardness of approximation for vertex-connectivity network-design problems. / Kortsarz, Guy; Krauthgamer, Robert; Lee, James R.
Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings. עורך / Klaus Jansen; Stefano Leonardi; Vijay Vazirani. Springer Verlag, 2002. עמוד 185-199 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); כרך 2462).

פרסום מחקרי: פרק בספר / בדוח / בכנס › פרסום בספר כנס › ביקורת עמיתים

TY - GEN

T1 - Hardness of approximation for vertex-connectivity network-design problems

AU - Kortsarz, Guy

AU - Krauthgamer, Robert

AU - Lee, James R.

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2002.

PY - 2002

Y1 - 2002

N2 - In the survivable network design problem SNDP, the goal is to find a minimum-cost subgraph satisfying certain connectivity requirements. We study the vertex-connectivity variant of SNDP in which the input specifies, for each pair of vertices, a required number of vertex-disjoint paths connecting them. We give the first lower bound on the approximability of SNDP, showing that the problem admits no efficient (formula presented) ratio approximation for any fixed ε > 0 unless NP ⊆ DTIME(npolylog(n)). We also show hardness of approximation results for several important special cases of SNDP, including constant factor hardness for the k-vertex connected spanning subgraph problem (k-VCSS) and for the vertex-connectivity augmentation problem, even when the edge costs are severely restricted.

AB - In the survivable network design problem SNDP, the goal is to find a minimum-cost subgraph satisfying certain connectivity requirements. We study the vertex-connectivity variant of SNDP in which the input specifies, for each pair of vertices, a required number of vertex-disjoint paths connecting them. We give the first lower bound on the approximability of SNDP, showing that the problem admits no efficient (formula presented) ratio approximation for any fixed ε > 0 unless NP ⊆ DTIME(npolylog(n)). We also show hardness of approximation results for several important special cases of SNDP, including constant factor hardness for the k-vertex connected spanning subgraph problem (k-VCSS) and for the vertex-connectivity augmentation problem, even when the edge costs are severely restricted.

UR - http://www.scopus.com/inward/record.url?scp=77951610564&partnerID=8YFLogxK

U2 - 10.1007/3-540-45753-4_17

DO - 10.1007/3-540-45753-4_17

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

AN - SCOPUS:77951610564

SN - 3540441867

SN - 9783540441861

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

SP - 185

EP - 199

BT - Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings

A2 - Jansen, Klaus

A2 - Leonardi, Stefano

A2 - Vazirani, Vijay

PB - Springer Verlag

T2 - 5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002

Y2 - 17 September 2002 through 21 September 2002

ER -

Kortsarz G, Krauthgamer R, Lee JR. Hardness of approximation for vertex-connectivity network-design problems. ב- Jansen K, Leonardi S, Vazirani V, עורכים, Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings. Springer Verlag. 2002. עמוד 185-199. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-45753-4_17

Hardness of approximation for vertex-connectivity network-design problems

תקציר

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

כנס

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

גישה למסמך

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

טביעת אצבע

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