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

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

Download (2.19 MB)
journal contribution
posted on 01.02.1987, 00:00 by Ajit Agrawal, Philip Klein, Ramamoorthi RaviRamamoorthi 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.

History

Date

01/02/1987

Usage metrics

Exports