ملخص
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 |
| المعرِّفات الرقمية للأشياء | |
| حالة النشر | نُشِر - 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, الولايات المتّحدة المدة: ٢٥ أغسطس ٢٠٠٨ → ٢٧ أغسطس ٢٠٠٨ |
سلسلة المنشورات
| الاسم | 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 |
| المدة | ٢٥/٠٨/٠٨ → ٢٧/٠٨/٠٨ |
ملاحظة ببليوغرافية
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).