Network Design with Metric Costs


Joseph Cheriyan University of Waterloo Canada


Wednesday, 29 July 2009 (All day)


  • A-212 (STCS Seminar Room)

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).