chapter  58
22 Pages

Approximating Minimum-Cost Connectivity Problems

We survey approximation algorithms and hardness results for versions of the Generalized Steiner Network (GSN) problem in which we seek to find a low-cost subgraph (where the cost of a subgraph is the sum of the costs of its edges) that satisfies prescribed connectivity requirements. These problems include the following well-known problems: min-cost k-flow, min-cost spanning tree, traveling salesman, directed/undirected Steiner tree, Steiner forest, k-edge/node-connected spanning subgraph, and others.