Approximating minimum-cost connectivity problems

We survey approximation algorithms and hardness results for versions of the Generalized Steiner Network (GSN) probleminwhichwe seek tofind 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.