On some network design problems with degree constraints

Rohit Khandekar, Guy Kortsarz, Zeev Nutov

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


We study several network design problems with degree constraints. For the minimum-cost Degree-Constrained 2-Node-Connected Subgraph problem, we obtain the first non-trivial bicriteria approximation algorithm, with 5b(v)+3 violation for the degrees and a 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((klogk)/Δ*)-approximation algorithm, where Δ* denotes the maximum degree in the optimum solution. We also give an Ω(logn) lower bound on approximating this problem. Then we consider the undirected version of this problem, however, with an extra diameter constraint, and give an Ω(logn) lower bound on the approximability of this version. We also consider a closely related Prize-Collecting Degree-Constrained Edge-Connectivity Survivable Network problem, and obtain several results in this direction by reducing the prize-collecting variant to the regular one. Finally, we consider the Terminal Steiner Tree problem, which is a simple variant of the Degree-Constrained Steiner Tree problem, when some terminals are required to be leaves. We show that this seemingly simple problem is equivalent to the Group Steiner Tree problem.

שפה מקוריתאנגלית
עמודים (מ-עד)725-736
מספר עמודים12
כתב עתJournal of Computer and System Sciences
מספר גיליון5
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - אוג׳ 2013

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

Funding Information:
* Corresponding author. E-mail addresses: rohitk@us.ibm.com (R. Khandekar), guyk@camden.rutgers.edu (G. Kortsarz), nutov@openu.ac.il (Z. Nutov). 1 Supported in part by NSF grant number 434923.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'On some network design problems with degree constraints'. יחד הם יוצרים טביעת אצבע ייחודית.

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