A typical problem in network design is to find a subgraph H of a given graph G such that H satisfies some connectivity requirements and has minimum cost. We give a constant-factor approximation algorithm for network design with node-connectivity requirements of zero or k, assuming that the edge costs satisfy the triangle inequalities (joint work with A.Vetta, McGill University).
