Network-design with degree constraints

Rohit Khandekar, Guy Kortsarz, Zeev Nutov

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

We study several network design problems with degree constraints. For the degree-constrained 2-connected subgraph problem we obtain a factor 6 violation for the degrees with 4 approximation for the cost. This improves upon the logarithmic degree violation and no cost guarantee obtained by Feder, Motwani, and Zhu (2006). Then we consider the problem of finding an arborescence with at least k terminals and with minimum maximum outdegree. We show that the natural LP-relaxation has a gap of Ω (√k) or Ω (n1/4) with respect to the multiplicative degree bound violation. We overcome this hurdle by a combinatorial O(√(k log k)/Δ*)-approximation algorithm, where Δ* denotes the maximum degree in the optimum solution. We also give an Ω(log n) lower bound on approximating this problem. Then we consider the undirected version of this problem, however, with an extra diameter constraint, and give an Ω(log n) lower bound on the approximability of this version. Finally, we consider a closely related prize-collecting degree-constrained Steiner Network problem. We obtain several results in this direction by reducing the prize-collecting variant to the regular one.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفApproximation, Randomization, and Combinatorial Optimization
العنوان الفرعي لمنشور المضيفAlgorithms and Techniques - 14th International Workshop, APPROX 2011 and 15th International Workshop, RANDOM 2011, Proceedings
الصفحات289-301
عدد الصفحات13
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2011
الحدث14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2011 and the 15th International Workshop on Randomization and Computation, RANDOM 2011 - Princeton, NJ, الولايات المتّحدة
المدة: ١٧ أغسطس ٢٠١١١٩ أغسطس ٢٠١١

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

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

!!Conference

!!Conference14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2011 and the 15th International Workshop on Randomization and Computation, RANDOM 2011
الدولة/الإقليمالولايات المتّحدة
المدينةPrinceton, NJ
المدة١٧/٠٨/١١١٩/٠٨/١١

بصمة

أدرس بدقة موضوعات البحث “Network-design with degree constraints'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا