Answers are grounded in this paper and cite their sources.
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 , j\ of nodes, an edgeconnectivity requirement rᵢⱼ. 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 + 1) of optimal, where r is the highest requirement value. In the course of proving the performance guarantee, we prove a combinatorial minmax 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.
No takes yet. Share an insight, caveat, or question.
Agrawal et al. (1995) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: