Authors
Ajit Agrawal, Philip Klein, Ramamoorthi Ravi
Publication date
1991/1/3
Book
Proceedings of the twenty-third annual ACM symposium on Theory of computing
Pages
134-144
Description
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 Tij. 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 lg R of optimal, where R is the highest requirement value.
In the course of proving the performance guarantee, we prove acombinatorial 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.
Total citations
Scholar articles
A Agrawal, P Klein, R Ravi - Proceedings of the twenty-third annual ACM …, 1991