When trees collide: an approximation algorithm for the generalized Steiner problem on networks
When trees collide: an approximation algorithm for the generalized Steiner problem on networks
复制标题
DOI：
10.1145/103418.103437
复制
发表时间：
1991-01
期刊：
影响因子：
--
通讯作者：
Exa Corporation;Brown University;University of California-Davis
中科院分区：
文献类型：
--
作者：
Exa Corporation;Brown University;University of California-Davis
我们给出了通用网络Steiner问题的第一个近似算法，这是网络设计中的问题。一个实例由一个带有链接成本的网络组成，对于节点的每对$ \ {i，j \} $，边缘连接性要求$ r_ {ij} $。目的是使用可用链接找到最低成本网络并满足要求。我们的算法输出了一个解决方案，其成本在$ 2 \ lceil \ log_2（r+1）\ rceil $ of Optimal $中，其中$ r $是最高要求值。在证明绩效保证的过程中，我们证明了一个组合Min-Max近似平等，将最低成本网络与某些剪裁的最大包装相关。由于该定理的证明，我们获得了一种近似算法，以最佳地包装这些切割。我们表明，该算法具有估计概率网络的可靠性的应用。
We give the first approximation algorithm for the generalized network Steiner problem, a problem in network design. An instance consists of a network with link-costs and, for each pair $\{i,j\}$ of nodes, an edge-connectivity requirement $r_{ij}$. The goal is to find a minimum-cost network using the available links and satisfying the requirements. Our algorithm outputs a solution whose cost is within $2\lceil \log_2(r+1)\rceil$ of optimal, where $r$ is the highest requirement value. In the course of proving the performance guarantee, we prove a combinatorial min-max approximate equality relating minimum-cost networks to maximum packings of certain kinds of cuts. As a consequence of the proof of this theorem, we obtain an approximation algorithm for optimally packing these cuts; we show that this algorithm has application to estimating the reliability of a probabilistic network.