Network Design with Metric Costs

Speaker: 

Joseph Cheriyan University of Waterloo Canada http://www.math.uwaterloo.ca/~jcheriya/

Time: 

Wednesday, 29 July 2009 (All day)

Venue: 

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