%0 DATA
%A Ajit, Agrawal
%A Philip, Klein
%A Ramamoorthi, Ravi
%D 1987
%T When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
%U https://kilthub.cmu.edu/articles/journal_contribution/When_Trees_Collide_An_Approximation_Algorithm_for_the_Generalized_Steiner_Problem_on_Networks/6709160
%R 10.1184/R1/6709160.v1
%2 https://kilthub.cmu.edu/ndownloader/files/12238460
%K approximation algorithm
%K network design
%K Steiner tree problem
%X 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[log_{2}(r + 1)] 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.