Tech Report CS-90-32
When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
Ajit Agrawal, Philip Klein and R. Ravi
December 1990
Abstract:
We give the first approximation algorithm for the {\em generalized network Steiner tree 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. 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 R $ 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.
(complete text in pdf or gzipped postscript)