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
المعرِّفات الرقمية للأشياء	https://doi.org/10.1007/3-540-45753-4_17
حالة النشر	نُشِر - 2002
منشور خارجيًا	نعم
الحدث	5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002 - Rome, إيطاليا المدة: ١٧ سبتمبر ٢٠٠٢ → ٢١ سبتمبر ٢٠٠٢

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

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

!!Conference

!!Conference	5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002
الدولة/الإقليم	إيطاليا
المدينة	Rome
المدة	١٧/٠٩/٠٢ → ٢١/٠٩/٠٢

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

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, إيطاليا, ١٧/٠٩/٠٢. 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

ملخص

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

!!Conference

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

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

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

بصمة

قم بذكر هذا