Network-Design with Degree Constraints
Network-Design with Degree Constraints
复制标题
具有度数约束的网络设计
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Zeev Nutov
中科院分区：
文献类型：
--
作者：
R. Khandekar;G. Kortsarz;Zeev Nutov
我们研究了几个网络设计问题，该学位限制了2个连接的子图问题，我们获得了6个违规的因子，而成本为4个近似值。 Motwani和Zhu（2006）。 LP - 释放的间隙为ω（√k）或ω（N1/4），相对于乘法绑定违规，我们通过组合O（√（k log k）/δ）克服了这一障碍。 ，其中δ*表示最佳解决方案中的最大程度。 ω（log n）较低最终，我们考虑了一个紧密相关的奖品，我们将奖励收集的变体降低到常规方向。
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.