When Trees Collide: An Approximation Algorithm for the Generalize.pdf.pdf' (2.19 MB)

When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

Download (2.19 MB)
journal contribution
posted on 01.02.1987 by Ajit Agrawal, Philip Klein, Ramamoorthi Ravi
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 rij. 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[log2(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.